HDU 3371 Connect the Cities （最小生成树+克鲁斯卡尔算法）

向右看齐 2022-06-12 01:15 175阅读 0赞

In 2100, since the sea level rise, most of the cities disappear. Though some survived cities are still connected with others, but most of them become disconnected. The government wants to build some roads to connect all of these cities again, but they don’t want to take too much money.

Input

The first line contains the number of test cases.  
Each test case starts with three integers: n, m and k. n (3 <= n <=500) stands for the number of survived cities, m (0 <= m <= 25000) stands for the number of roads you can choose to connect the cities and k (0 <= k <= 100) stands for the number of still connected cities.  
To make it easy, the cities are signed from 1 to n.  
Then follow m lines, each contains three integers p, q and c (0 <= c <= 1000), means it takes c to connect p and q.  
Then follow k lines, each line starts with an integer t (2 <= t <= n) stands for the number of this connected cities. Then t integers follow stands for the id of these cities.

Output

For each case, output the least money you need to take, if it’s impossible, just output -1.

Sample Input

1
    6 4 3
    1 4 2
    2 6 1
    2 3 5
    3 4 33
    2 1 2
    2 1 3
    3 4 5 6

Sample Output

题解：

我从未见过如此厚颜无耻之题。。。卡内存卡时间，还是道水题，典型的最小生成树的题，用克鲁斯卡尔算法，先并查集连好点，然后日常操作，我比赛的时候怎么交都是爆内存。。比完赛才发现把优先队列改成数组拍一下序就不会爆内存了。。。神坑，而且过的时候还是998ms。。。差2ms就没过，为什么有这种坑题，后来问学长是因为优先队列比较耗内存。。。先让我哭一会

代码：

#include<iostream>
    #include<stdio.h>
    #include<string>
    #include<cstring>
    #include<map>
    #include<queue>
    #include<stack>
    #include<algorithm>
    #include<math.h>
    #include<deque>
    #include<stack>
    using namespace std;
    int m,n,k,tot;
    struct edge
    {
        int f,t;
        int v;
    };
    int cmp(const edge& x,const edge& y)
    {
        return x.v<y.v;
    }
    edge a[25005];
    int pre[505];//保存根节点
    int find(int x)//寻找更节点，压缩路径
    {
        if(x!=pre[x])
            pre[x]=find(pre[x]);
        return pre[x];
    }
    void init()
    {
        int i,j;
        for(i=1;i<=n;i++)
        {
            pre[i]=i;//初始化根节点
        }
    }
    int main()
    {
        int i,j,test,d1,z,d2,s;
        edge t;
        scanf("%d",&test);
        while(test--)
        {
            s=0;
            scanf("%d%d%d",&n,&m,&k);
            init();
            tot=0;
            for(i=0;i<m;i++)
            {
                scanf("%d%d%d",&t.f,&t.t,&t.v);
                a[i]=t;
            }
            for(i=0;i<k;i++)
            {
                int x,y;
                scanf("%d",&x);
                scanf("%d",&y);//吓得我不敢开内存
                d1=find(y);
                for(j=1;j<x;j++)
                {
                    scanf("%d",&z);
                    d2=find(z);
                    if(d1!=d2)
                    {
                        pre[d2]=d1;
                        tot++;
                    }
                }
            }
            sort(a,a+m,cmp);//为了贪心排序
            for(i=0;i<m;i++)
            {
                t=a[i];
                d1=find(t.f);
                d2=find(t.t);
                if(d1!=d2)//并查集操作
                {
                    s+=t.v;
                    tot++;//边数加一
                    pre[d2]=d1;
                }
                if(tot>=n-1)//生成树建好
                    break;
            }
            if(tot>=n-1)
                printf("%d\n",s);
            else
                printf("-1\n");
        }
        return 0;
    }