最小生成树升级版

刚开始我就傻眼了！！！

题目给的数据实在是不好调试，最后还是看的大佬的代码才理解的

题目分析：
1.首先代码几乎和最小生成树差不多，但是题目的意思要明白，如果形成唯一的最小生成树至少要去掉多少边的权值和，我们要明白为什么一个图里面有多条最小生成树，唯一的原因就是相同权值的边有多条，因为是最小嘛所以只可能是这一种情况。

2.接着我们要明白，我们求最小生成树，首先要对权值进行从小到大进行排序，不断地加入排序后最小的边，直到形成一颗最小生成树为止。

3.紧接着我们统计一下相同权值的边一共有多少条，如果这条边的两点都不在这颗最小生成树里面那么就把它们都先加起来，再遍历一次，我们把这条边的两点合并，如果他们足以构成一颗最小生成树的边那么就减去它，其实到最后我们减去的就是一颗最小生成树的权值的总和，那么剩下的就是我们要得出的答案，相当于所有的边的和减去唯一最小生成树的权值和就是答案

这里给出两种代码

代码一：下标从一开始

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int f[maxn];
struct node
{
    int u, v, w;
    bool operator<(const node x)
    {
        return w < x.w;
    }
} e[maxn];

int find(int x)
{
    return f[x] == x ? x : f[x] = find(f[x]);
}
int main()
{
    int n, m, ans = 0;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        f[i] = i;
    for (int i = 1; i <= m; ++i)
        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
    sort(e + 1, e + m + 1);
    for (int i = 1; i <= m; ++i)
    {
        int l = i, r = i;
        while (r <= m && e[i].w == e[r + 1].w)
            ++r;
        for (int j = l; j <= r; ++j)
        {
            int a = find(e[j].u), b = find(e[j].v);
            if (a != b)
                ans += e[j].w;
        }
        for (int j = l; j <= r; ++j)
        {
            int aa = find(e[j].u), bb = find(e[j].v);
            if (aa != bb)
                f[aa] = bb, ans -= e[j].w;
        }
    }
    printf("%d\n", ans);
}

代码二：下边从0开始

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int f[maxn];
struct node
{
    int u, v, w;
    bool operator<(const node x)
    {
        return w < x.w;
    }
} e[maxn];

int find(int x)
{
    return f[x] == x ? x : f[x] = find(f[x]);
}
int main()
{
    int n, m, ans = 0;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        f[i] = i;
    for (int i = 0; i < m; ++i)
        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
    sort(e, e + m);
    for (int i = 0; i < m; ++i)
    {
        int l = i, r = i;
        while (r < m && e[i].w == e[r].w)
            ++r;
        for (int j = l; j < r; ++j)
        {
            int a = find(e[j].u), b = find(e[j].v);
            if (a != b)
                ans += e[j].w;
        }
        for (int j = l; j < r; ++j)
        {
            int aa = find(e[j].u), bb = find(e[j].v);
            if (aa != bb)
                f[aa] = bb, ans -= e[j].w;
        }
    }
    printf("%d\n", ans);
}

读者可以根据自己的喜好选择一个，代码大致相同，就是细节部分需要处理一下