HDU 3371 Connect the Cities

题意：给你n m k; 最小生成树的经典输入，k的意思代表给定有k条路已经连通了。现在要你求出连通所有路的最小价值

思路：最小生成树的变形，只要用并查集把已经连通的点放到一起就可以了，再最小生成树算法

AC代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,cnt;
int f[520];
int flag[520];
#define N 25005
struct node
{
    int u,v,w;
}num[N];

bool cmp(node x,node y)
{
    return x.w<y.w;
}

int find(int x)
{
    if(x!=f[x])
        f[x]=find(f[x]);
    return f[x];
}

int kruscal()
{
    int x,y,i;
    //int dian=n;
    int sum=0;
    for(i=0;i<cnt;i++)
    {
        x=find(num[i].u);
        y=find(num[i].v);
        if(x==y)
            continue;
        sum+=num[i].w;
        f[x]=y;
        flag[num[i].u]=1;
        flag[num[i].v]=1;
      /*  dian--;
        if(dian==0)
            break;*/
    }
  /*  if(i==cnt)
        return -1;*/
 //   else
        return sum;
}
int main()
{
    int k,i,j,sum;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        cnt=0;
        scanf("%d %d %d",&n,&m,&k);
        memset(flag,0,sizeof(int)*(n+2));
        for(i=0;i<=n;i++)
            f[i]=i;
        for(i=0;i<m;i++)
        {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            num[cnt].u=a;
            num[cnt].v=b;
            num[cnt++].w=c;

        }
        sort(num,num+cnt,cmp);
        for(i=0;i<k;i++)
        {
            int a,b;
            int test;
            scanf("%d",&test);
            scanf("%d",&a);
            flag[a]=1;
            for(j=1;j<test;j++)
            {
                scanf("%d",&b);
                flag[b]=1;
                int x=find(a);
                int y=find(b);
                if(x!=y)
                    f[x]=y;
            }
        }
        sum=kruscal();
        for(i=1;i<=n;i++)
            if(!flag[i])
                break;
        if(i<=n)
            printf("-1
");
        else
            printf("%d
",sum);
    }
    return 0;
}