题解：最小生成树…………
|
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
27
28
29
30
31 |
#include <cstdio>#include <algorithm>using
namespace std;struct
node{int
a,b,l;}seg[900];int f[27],m,n,a,b; 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
scanc(int
&x){ while(c=getchar(),c<‘A‘||c>‘Z‘);x=c-‘A‘;}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,t=0,cnt=n-1; for(int
i=0;i<=n;i++)f[i]=i; for(int
i=0;i<n-1;i++){ scanc(a);scan(m); for(int
j=0;j<m;j++)seg[t].a=a,scanc(seg[t].b),scan(seg[t++].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 1301 Jungle Roads,布布扣,bubuko.com
原文：http://www.cnblogs.com/forever97/p/3603327.html