Dutor

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
struct Edge 
{
	int from, to, w; //~ 不要被假象迷惑，这里是无向图
	Edge(int f, int t, int _w): from(f), to(t), w(_w){}
	/*
	//~ bool operator <(const Edge& e){ return w < e.w; }
	bool operator >(const Edge& e){ return w > e.w; }
	*/
};
//~ 为什么我把operator<重载为成员会出错？
//~ bool operator <(const Edge& e1, const Edge& e2){ return e1.w < e2.w; }
bool operator >(const Edge& e1, const Edge& e2){ return e1.w > e2.w; } 
bool AddEdge(vector<int> & V, const Edge& e);
int main(int argc, char* argv[])
{
	vector<Edge> E;
	int from, to, w;
	int n; //~ 顶点数
	cin>>n;
	vector<int> V(n+1, -1); //~ 顶点并查集
	while (cin>>from>>to>>w) E.push_back(Edge(from, to, w));
 
	make_heap(E.begin(), E.end(), greater<Edge>());
	int count = 0; //~ 已添加边数
	while (E.size())
	{
		Edge e = E[0];
		if(AddEdge(V, e)) //~ 将成功添加的边输出
		{
			count++;
			if(count == n - 1) break; //~ 树已生成完毕
			cout<<e.from<<"->"<<e.to<<": "<<e.w<<endl;
		}
		pop_heap(E.begin(), E.end(),greater<Edge>());
		E.pop_back();
	}
	if (count != n - 1) cout<<"I cannot do what you want."<<endl;
	return 0;
}
 
bool AddEdge(vector<int> & V, const Edge& e)
{
	int i = e.from;
	for (; V[i] > 0;) i = V[i]; //~ 寻找根节点
	int j = e.to;
	for (; V[j] > 0;) j = V[j]; //~ 寻找根节点
	if (i == j)	return false; //~ i,j两节点已经联通
	if (V[i] > V[j]) //~ 将小集合合并至大集合上
	{
		V[i] = j;
		V[j] += V[i];
	}
	else
	{
		V[j] = i;
		V[i] += V[j];
	}
	return true; //~ ^_^
}