hdu3371 Connect the Cities

#include<stdio.h>
#include<algorithm>
using namespace std;

int n;
int pre[505];
struct Node
{
    int v1,v2,dis;
};
Node node[25005];

void initial()
{
    for(int i=1;i<=n;i++) pre[i]=0;
}

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

bool merge(int v1,int v2)
{
    int root1=find(v1);
    int root2=find(v2);

    if(root1==root2) return false;
    if(root1>root2) pre[root1]=root2;
    else pre[root2]=root1;
    return true;
}

int cmp(const void *a,const void *b)
{
    return (*(Node*)a).dis-(*(Node*)b).dis;
}

int exist()
{
    int sum=0;
    for(int i=1;i<=n;i++) if(!pre[i]) sum++;
    return sum;
}

int main()
{
    int cases;
    scanf("%d",&cases);
    while(cases--)
    {
        int k,m;
        scanf("%d%d%d",&n,&m,&k);
        initial();
        for(int i=0;i<m;i++)
            scanf("%d%d%d",&node[i].v1,&node[i].v2,&node[i].dis);

        int size,v1,v2;
        for(int i=0;i<k;i++)
        {
            scanf("%d%d%d",&size,&v1,&v2);
            merge(v1,v2);
            for(int j=0;j<size-2;j++)
            {
                scanf("%d",&v2);
                merge(v1,v2);
            }
        }

        qsort(node,m,sizeof(Node),cmp);
        int sum=0;
        for(int i=0;i<m;i++)
            if(merge(node[i].v1,node[i].v2)) sum+=node[i].dis;

        if(exist()==1) printf("%d\n",sum);
        else printf("-1\n");
    }
    return 0;
}

总结：

本题首先是要判断是否能构成连通图，若能构成连通图，在计算构成连通图后最小生成树代价，可以先假设
能构成连通图，在通过Kruskal算法求出最小生成树代价，之后再根据Kruskal算法算出的点集的个数来验证
先前的假设是否成立。