最小生成树模板题 hpu 积分赛 Vegetable and Road again

问题 H: Vegetable and Road again

时间限制: 1 Sec 内存限制: 128 MB

提交: 19 解决: 8

题目描述

修路的方案终于确定了。市政府要求任意两个公园之间都必须实现公路交通（并不一定有直接公路连接，间接公路相连也可以）。但是考虑到经济成本，市政府希望钱花的越少越好。

你能帮助Vegetable找到给出的修路方案所需的最少花费吗？

输入

有T组测试数据。

每组包含一组N(0<n<=100)和M，N表示有N个公园，M表示这N个公园间的M条路。

接下来给出M行，每行包括A，B, C。表示A和B之间修公路需要花费C元。

输出

若给出的方案可行，输出该方案最小需要的花费，若给出的方案不可行，输出Wrong。

样例输入

1
4 3
1 2 1
2 3 2
3 4 3

样例输出

6

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn = 1005;

int f[maxn];

struct edge
{
    int from;
    int to;
    int cost;
    friend bool operator < (edge a,edge b)
    {
        return a.cost < b.cost;
    }
}e[maxn];

void ufs(int n)
{
    for(int i = 1; i <= n; i++)
        f[i] = i;
}

int findd(int x)
{
    if(f[x] == x)
        return x;
    else return findd(f[x]);
}

void merger(int x,int y)
{
    int fx = findd(x);
    int fy = findd(y);
    if(fx != fy)
        f[fy] = fx;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        ufs(n);
        int cnt = 0;
        for(int i = 0; i < m; i++)
            scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].cost);
        sort(e,e + m);
        for(int i = 0; i < m; i++)
        {
            if(findd(e[i].from) != findd(e[i].to))
            {
                merger(e[i].from,e[i].to);
                cnt += e[i].cost;
            }
        }
        int flag = 1;
        for(int i = 1; i < n; i++)
        {
            if(findd(f[i]) != findd(f[i + 1]))
            {
                flag = 0;
                printf("Wrong
");
                break;
            }
        }
        if(flag)
            printf("%d
",cnt);
    }
    return 0;
}