06 复试 还是畅通工程

给出m个城镇，两两间距离，问最短路能全连通的路程。

最小生成树，基本并查集问题。贪心，总取最短的路尝试，如果两点不在一起则连通。
kruskal 算法。

#include<iostream>
using namespace std;
#include<vector>
#include<memory.h>
#include<algorithm>

struct Road
{
	int start;
	int end;
	int dis;
};

bool compare(Road a,Road b)
{
	return a.dis<b.dis;
}
vector<Road> road;
int city[101];

int find(int pos)
{
	if(city[pos]==-1)
		return pos;
	return city[pos]=find(city[pos]);
}


int merge(int a,int b)
{
	int roota=find(a);
	int rootb=find(b);
	if(roota==rootb)
		return 0;
	city[roota]=rootb;
	return 1;
}

int kruskal(vector<Road> road)
{
	int sum = 0;
	int root1;
	int root2;
	sort(road.begin(),road.end(),compare);
	for(int i=0;i<road.size();i++)
	{
		root1 = find(road[i].start);
		root2 = find(road[i].end);
		if(root1!=root2)
		{
			merge(road[i].start,road[i].end);
			sum+=road[i].dis;
		}
	}
	return sum;

}


int main()
{
	int n;
	while(1)
	{
		cin>>n;
		road.clear();
		memset(city,-1,sizeof(city));
		if(n==0)
			break;
		n=n*(n-1)/2;
		while(n--)
		{
			Road r;
			cin>>r.start;
			cin>>r.end;
			cin>>r.dis;
			road.push_back(r);
		}
		cout<<kruskal(road)<<endl;
	}

}