/*可用“破圈法”求解帶權連通無向圖的一棵最小代價生成樹。所謂“破圈法”就是“任取一圈，去掉圈上權最大的邊”，反復執行這一步驟，直到沒有圈為止。請給出用“破圈法”求解給定的帶權連通無向圖的一棵最小代價生成樹的詳細算法，并用程序實現你所給出的算法。注：圈就是回路。*/
#include?
#include?
using?namespace?std;
template
class?MaxHeap
{
private:
	T?*?heapArray;
	int?CurrentSize;
	int?MaxSize;
public:
	MaxHeap（int?N）;
	void?BuildHeap（）;
	bool?Insert（T?N）;
	void?RemoveMax（）;
	void?SiftDown（int?left）;
	void?SiftUp（int?position）;
	bool?IsEmpty（）;
	T?GetMax（）;
};
template
MaxHeap::MaxHeap（int?N）
{
	MaxSize?=?N;
	heapArray?=?new?T[MaxSize];
	CurrentSize?=?0;
}
template
T?MaxHeap::GetMax（）
{
	return?heapArray[0];
}
template
bool?MaxHeap::IsEmpty（）
{
	if（CurrentSize?==?0）
		return?1;
	else
		return?0;
}
template
void?MaxHeap::RemoveMax（）
{
	if?（CurrentSize>0）
	{
		CurrentSize--;
		heapArray[0]?=?heapArray[CurrentSize];
		SiftDown（0）;
	}
	else
	{
		cout<<“堆空“<	}
}
template
void?MaxHeap::BuildHeap（）
{
	for?（int?i?=?CurrentSize/2-1?;?i?>=0?;?i--）
	{
		SiftDown（i）;
	}
}

template
void?MaxHeap::SiftDown（int?left）
{
	int?i?=?left;
	int?j?=?2*i?+1;
	T?temp?=?heapArray[i];
	while?（j?	{
		if?（（j?		{
			j++;
		}
		if?（temp.weight		{
			heapArray[i]?=?heapArray[j];
			heapArray[j]?=?temp;
			i?=?j;
			j?=?2*j?+?1;
		}
		else?
			break;
	}
	heapArray[i]?=?temp;
}
template
void?MaxHeap::SiftUp（int?position）
{
	int?i?=?position;
	int?j?=?（i-1）/2;
	T?temp?=?heapArray[i];
	while?（heapArray[j].weight?	{
		temp?=?heapArray[i];
		heapArray[i]?=?heapArray[j];
		heapArray[j]?=?temp;
		i?=?j;
		j?=?（i-1）/2;
	}
	heapArray[i]?=?temp;
}
template
bool?MaxHeap::Insert（T?N）
{
	if?（CurrentSize	{
		CurrentSize++;
		heapArray[CurrentSize-1]?=?N;
		SiftUp（CurrentSize-1）;
		return?1;
	}
	else
	{
		cout<<“元素已滿“<		return?0;
	}
}
template
class?Edge
{
public:
	int?start?;
	int?over;
	T?weight;
	Edge（）{start?=?over?=?weight?=0;}
	Edge（int?sint?oT?w）{start?=?s;over?=?o;?weight?=?w;}
};
template
class?Graph
{
public:
	int?vertexNum;
	int?edgeNum;
	int?*?Mark;
	Graph（int?verticesNum）;
	~Graph（）;
	virtual?void?Create（）?=?0;
	virtual?Edge?FirstEdge（int?oneVertex）?=?0?;
	virtual?Edge?NextEdge（Edge?oneEdge）?=?0;
	virtual?int?BFS（int?v）?=?0;
	int?VerticesNum（）{return?vertexNum;}
	int?EdgesNum（）{return?edgeNum;}
	bool?IsEdge（Edge?oneEdge）;
	int?StartVertex（Edge?oneEdge）{return?oneEdge.start;}
	int?EndVertwx（Edge?oneEdge）{return?oneEdge.over;}
	T?Weight（Edge?oneEdge）{return?oneEdge.weight;}
	virtual?void?SetEdge（int?start?int?over?int?weight）?=?0;
	virtual?void?DelEdge（int?start?int?over?）?=?0?;
	virtual?void?Initialize（）?=?0;
};
template
Graph::Graph（int?verticesNu