复试前练手...HDOJ - 3371 kruskal模板题...
上周水了一场腾讯马拉松....水爆了..手速赛..囧...
本题...kruskal模板题...恶心的是C++能过..G++超时！！
#include<iostream>#include<stdio.h>#include<string.h>#include<stack>#include<queue>#include<map>#include<cmath>#include<set>#define oo 1000000000using namespace std;struct node{ int p,q,c;}line[30000];int t,n,m,k,father[505],ans;bool cmp(node a,node b){ return a.c<b.c;}int getfather(int k){ if (father[k]!=k) father[k]=getfather(father[k]); return father[k];}int main(){ int i,j,h,x,y; scanf("%d",&t); while (t--) { scanf("%d%d%d",&n,&m,&k); for (i=1;i<=n;i++) father[i]=i; ans=0; for (i=1;i<=m;i++) scanf("%d%d%d",&line[i].p,&line[i].q,&line[i].c); while (k--) { scanf("%d%d",&h,&x); x=getfather(x); h--; while (h--) { scanf("%d",&y); father[getfather(y)]=x; } } sort(line+1,line+1+m,cmp); ans=0; for (i=1;i<=m;i++) if (getfather(line[i].q)!=getfather(line[i].p)) { ans+=line[i].c; father[father[line[i].q]]=father[line[i].p]; } for (i=2;i<=n;i++) if (getfather(1)!=getfather(i)) ans=-1; printf("%d\n",ans); } return 0;}