复试前练手...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;}