【BUAA 933】拮据的模拟城市
最小生成树 Kruskal 注意双向路径 有道题就没考虑双向活生生坑了。。。
代码如下
;typedef struct Edge{int u,v,d;Edge a)const{return d < a.d;}}Edge;Edge eg[111111];int pre[1111];int n,tp;void Init(){int i;for(i = 1; i <= n; ++i)pre[i] = i;}int Find(int x){if(x != pre[x]) pre[x] = Find(pre[x]);return pre[x];}void Add(int u,int v,int d){eg[tp].u = u;eg[tp].v = v;eg[tp++].d = d;}int main(){int i,u,v,d,cnt,sum,k,m,r;while(~scanf(“%d %d”,&n,&m)){tp = 0;Init();while(m–){scanf(“%d %d %d”,&u,&v,&d);Add(u,v,d);}sort(eg,eg+tp);cnt = sum = 0;for(i = 0; i < tp; ++i){k = Find(eg[i].u);r = Find(eg[i].v);if(k != r){pre[k] = r;sum += eg[i].d;cnt++;}if(cnt == n-1) break;}printf(“%d\n”,sum);}return 0;}
，你会发现，曾经以为很难做到的事情，
