Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 12557 Accepted Submission(s): 3453
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<cstdlib> #include<vector> using namespace std; struct node { int x,y,w; }e[25005]; int n,m,k,cnt,fa[25005]; /* int find(int x) { if(x!=fa[x]) fa[x]=find(fa[x]); return fa[x]; } */ int find(int x) { while(x!=fa[x]) x=fa[x]; return fa[x]; } int Union(int x,int y) { if(x==-1) return 0; int fx,fy; bool flag=false; fx=find(x),fy=find(y); if(fx!=fy) { --cnt; fa[fx]=fy; flag=1; } return flag; } bool cmp(node a,node b) { return a.w<b.w; } int main() { int tt; scanf("%d",&tt); while(tt--) { int ans=0; scanf("%d%d%d",&n,&m,&k); cnt=n-1; for(int i=0;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w); for(int i=0;i<k;i++) { int a,c,pre=-1; scanf("%d",&a); while(a--) { scanf("%d",&c); Union(pre,c); pre=c; } } sort(e+1,e+1+m,cmp); for(int i=1;i<=m;i++) { if(Union(e[i].x,e[i].y)==1) ans+=e[i].w; } if(cnt!=0) printf("-1\n"); else printf("%d\n",ans); } return 0; }
原文:http://www.cnblogs.com/water-full/p/4510002.html