HDU 1233 还是畅通工程 （最小生成树 Kruskal）

思路：

基本的最小生成树模板题。

AC代码：

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; int node[110]; int _find(int x){ int xx = x; while(node[xx] != xx){ xx = node[xx]; } int temp; while(x != xx){ temp = node[x]; node[x] = xx; x = temp; } return xx; } bool _merge(int x,int y){ int xx = _find(x); int yy = _find(y); if(xx != yy){ node[yy] = xx; return false; } else{ return true; } } struct edge{ int from,to,v; }e[10000]; bool cmp(const edge &a,const edge &b){ return a.v < b.v; } int main() { int n,m; while(scanf("%d",&n),n){ int m = n*(n-1)/2; for(int i = 1;i <= 100;i++){ node[i] = i; } for(int i = 1;i <= m;i++){ scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].v); // 注意得没有重边，否则这样输入就错了 } sort(e+1,e+1+m,cmp); long long int ans = 0; for(int i = 1;i <= m;i++){ if(_merge(e[i].from,e[i].to) == false){ ans += e[i].v; } } printf("%I64d\n",ans); } return 0; }