Time Limit: 2000/1000 MS
(Java/Others) Memory Limit: 32768/32768 K
(Java/Others)
Total Submission(s): 7997 Accepted
Submission(s): 2267
代码:
#include<stdio.h> #include<string.h> #include<stdlib.h> #define maxn 25005 typedef struct Side { int vs; int ve; int cost; }side; side sta[maxn]; int father[505],rank[505]; void init(int n) { for(int i=0 ;i<n ; i++) { father[i]=i; rank[i]=1; } } int setfind(int x) { if(x!=father[x]) father[x]=setfind(father[x]); return father[x]; //这里不能用x } void krusal(int a,int b) { int x=setfind(a); int y=setfind(b); if(x==y) return ; if(x<y) { father[y]=x; rank[x]+=rank[y]; } else { father[x]=y; rank[y]+=rank[x]; } } int cmp(const void* a , const void* b) { return (*(side*)a).cost-(*(side*)b).cost; } int main() { int test,n,m,k,i,ans; scanf("%d",&test); while(test--) { ans=0; scanf("%d%d%d",&n,&m,&k); init(n); for(i=0; i<m ;i++) { scanf("%d%d%d",&sta[i].vs,&sta[i].ve,&sta[i].cost); } int a,b,c; for(i=0;i<k ;i++) { scanf("%d",&c); scanf("%d",&a); while(c-- >1) { scanf("%d",&b); krusal(a,b); } } qsort(sta,m,sizeof(sta[0]),cmp); for(i=0; i<m ;i++) { int tem1=setfind(sta[i].vs); int tem2=setfind(sta[i].ve); if(tem1 != tem2) { krusal(tem1,tem2); ans+=sta[i].cost; } } if(rank[0]==n) printf("%d\n",ans); else printf("-1\n"); } return 0; }
HDUOJ---3371Connect the Cities,布布扣,bubuko.com
HDUOJ---3371Connect the Cities
原文:http://www.cnblogs.com/gongxijun/p/3570473.html