#include<iostream> #include<algorithm> using namespace std; const int N=110,M=1e6+10; int p[N],n; int find(int x) { if(x!=p[x]) p[x]=find(p[x]); return p[x]; } struct Edge { int a,b,w; }q[M]; bool cmp(Edge a,Edge b) { return a.w<b.w; } int main() { int m; cin>>n; while(n) { int cost=0; for(int i=1;i<=n;i++) p[i]=i; m=(n-1)*n/2; for(int i=0;i<m;i++) { int a,b,w; cin>>a>>b>>w; q[i].a=a,q[i].b=b,q[i].w=w; } sort(q,q+m,cmp); for(int i=0;i<m;i++) { int a=find(q[i].a),b=find(q[i].b); if(a!=b) { p[a]=b; cost+=q[i].w; } } cout<<cost<<endl; cin>>n; } return 0; }
解题思路:
注意事项:
参考代码:
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:535 |
C语言程序设计教程(第三版)课后习题6.3 (C++代码)浏览:949 |
【计算两点间的距离】 (C语言代码)浏览:1473 |
用筛法求之N内的素数。 (C语言代码)浏览:664 |
母牛的故事 (C语言代码)浏览:549 |
有关字符,字符串的输入输出函数说明浏览:478 |
矩形面积交 (C++代码)浏览:1127 |
循环入门练习6 (C语言代码)浏览:953 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:401 |
简单的a+b (C语言代码)浏览:531 |