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;}}