题解：最小生成树
|
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
32
33
34
35
36 |
#include <cstdio>#include <algorithm>using
namespace std;struct
node{int
a,b,l;}seg[25005];int T,z,x,t,f[505],m,n,k; 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(){ scan(T); while(T--){ scan(n),scan(m),scan(k); int
ans=0; for(int
i=1;i<=n;i++)f[i]=i; int
cnt=n-1; for(int
i=0;i<m;i++)scan(seg[i].a),scan(seg[i].b),scan(seg[i].l); while(k--){ scan(t);scan(x); int
q=sf(x); for(int
i=1;i<t;i++){ scan(z); int
w=sf(z); if(q!=w)f[w]=q,cnt--; } }sort(seg,seg+m,cmp); for(int
i=0;i<m&&cnt;i++){ int
q=sf(seg[i].a),w=sf(seg[i].b); if(q!=w)cnt--,f[q]=w,ans+=seg[i].l; } if(cnt)puts("-1");else
printf("%d\n",ans); } return
0;} |
HDU 3371 Connect the Cities,布布扣,bubuko.com
原文：http://www.cnblogs.com/forever97/p/3603393.html