1 #include
      
         2 #include
       
          3 struct data{
     4     int st,fi,v;  5 }a[25010];  6 int i,j,res,ans,file,t,w1,w,father1,father2,father[510],n,m,k,flag;  7 void qsort1(int l,int r)  8 {
     9     int i=l,j=r,t=a[(l+r)/2].v; 10     struct data change; 11     do{
    12         while (a[i].v
        
         t) j--; 14         if (i<=j) 15         {
    16             change=a[i]; 17             a[i]=a[j]; 18             a[j]=change; 19             i++; 20             j--; 21         } 22     }while (i<=j); 23     if (l
         
          0) 45             {
    46                 scanf("%d",&w); 47                 father1=getfather(w); 48                 for (j=2;j<=t;j++) 49                 {
    50 51                     scanf("%d",&w1); 52                     father[getfather(w1)]=father1; 53                 } 54             } 55         } 56         for (i=1;i<=n;i++) 57             if (father[i]!=i) 58             {
    59                 res++; 60             } 61         qsort1(1,m); 62         i=1; 63         while (res
          
           m) 75             {
    76                 printf("-1\n"); 77                 flag=1; 78                 break; 79             } 80         } 81         if (flag)continue; 82         printf("%d\n",ans); 83     } 84     return 0; 85 }
          
         
        
       
      

题目大意：n个城市，中间可建立m条路，且其中有k组城市已联通，问将所有城市都联通的最小代价。

大体思路：相当于是求一个部分路权为0的最小生成树。可以用Kruskal算法+并查集+排序优化。如果用并查集做的话应该可以直接将n组城市分别合到n个集合中。

注意事项：并查集合并时取“最父亲”的那个父亲，即root。