ACM模版

描述

题解

其实这个题简单的有些让人不敢写，因为资格赛应该是没有签到题的……一直怀疑自己是不是读错题了，或者没有搞懂它真正的意图。

其实就是判断一下连通性，一个并查集就好了，如果一开始就没有联通，那么结果就是 0 ，如果是连通的，我们只消的将某一个点删掉即可，这个点是哪个呢？就是和他连通的边的权值和最小的点。

感觉真的好简单，但是看到 AC 人数那么少，真是不敢写……然后强势懵一波，就这样， A <script type="math/tex" id="MathJax-Element-58">A</script> 了~~~

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

#define clr(a, b) memset(a, b, sizeof(a))

using namespace std;

const int MAXN = 3333;

int n, m;
int val[MAXN];
int pre[MAXN];

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

int main(void)
{
    while (~scanf("%d%d", &n, &m))
    {
        clr(pre, 0);
        clr(val, 0);

        int cnt = n - 1;
        int u, v, w, u_, v_;
        for (int i = 1; i <= m; i++)
        {
            scanf("%d%d%d", &u, &v, &w);
            if (u == v)
            {
                continue;
            }

            val[u] += w;
            val[v] += w;
            u_ = find(u);
            v_ = find(v);
            if (u_ != v_)
            {
                pre[u_] = v_;
                cnt--;
            }
        }

        if (cnt == 0)
        {
            sort(val + 1, val + n + 1);
            printf("%d\n", val[1]);
        }
        else
        {
            printf("0\n");
        }
    }

    return 0;
}