题解：最小生成树
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 |
#include <cstdio>#include <algorithm>using
namespace std;struct
node{int
a,b,l;}seg[10000];int f[105],m,n; char
c;int sf(int
x){return
f[x]==x?x:f[x]=sf(f[x]);}bool
cmp(node a,node b){return
a.l<b.l;}void
scan(int
&x){ while(c=getchar(),c<‘0‘||c>‘9‘);x=c-‘0‘; while(c=getchar(),c>=‘0‘&&c<=‘9‘)x=x*10+c-‘0‘;}int
main(){ while(~scanf("%d",&n)){ if(n==0)break;int
ans=0; for(int
i=0;i<=n;i++)f[i]=i; int
t=n*(n-1)/2,cnt=n-1; for(int
i=0;i<t;i++)scan(seg[i].a),scan(seg[i].b),scan(seg[i].l); sort(seg,seg+t,cmp); int
i=-1; while(cnt){ int
q=sf(seg[++i].a),w=sf(seg[i].b); if(q!=w)cnt--,f[q]=w,ans+=seg[i].l; } printf("%d\n",ans); } return
0;} |
HDU 1233 还是畅通工程,布布扣,bubuko.com
原文：http://www.cnblogs.com/forever97/p/3603294.html