最大生成树

题目分析：第一次遇见最大生成树的题目，但是它的代码几乎和最小生成树一模一样，唯一不同的就是在排序的时候把最大的边放在前面，那么我们选择的时候就是从最大的边开始，这样一来，遍历完之后，最大生成树就求出来了，刚开始看见这个题目的时候，没看懂最后一句话，说的是dis（u，v）表示路径中的最短的边的边权，但是选择的时候又选择最大的路径，反反复复不是很理解，一看题解，原来是一个最大生成树问题，也就是说在构成通路的基础上，每条边选择最大的边权。

方法一：直接建树

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
int pre[maxn];
struct node
{
    int a, b, c;
    bool operator<(const node x) const
    {
        return c > x.c;
    }
} w[maxn];

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

void join(int x, int y)
{
    pre[find(x)] = find(y);
}
int main()
{
    int n, m;
    while (~scanf("%d%d", &n, &m))
    {
        ll ans = 0;
        for (int i = 1; i <= n; ++i)
            pre[i] = i;
        for (int i = 1; i <= m; ++i)
            scanf("%d%d%d", &w[i].a, &w[i].b, &w[i].c);
        sort(w + 1, w + m + 1);
        for (int i = 1; i <= m; ++i)
            if (find(w[i].a) != find(w[i].b))
            {
                join(w[i].a, w[i].b);
                ans += w[i].c;
            }
        printf("%lld\n", ans);
    }
    return 0;
}

方法二：先判断再加边

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
int pre[maxn];
struct node
{
    int a, b, c;
    bool operator<(const node x) const
    {
        return c > x.c;
    }
} w[maxn];

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

int join(int x, int y)
{
    int a = find(x);
    int b = find(y);
    if (a != b)
    {
        pre[a] = b;
        return 1;
    }
    return 0;
}
int main()
{
    int n, m;
    while (~scanf("%d%d", &n, &m))
    {
        ll ans = 0;
        for (int i = 1; i <= n; ++i)
            pre[i] = i;
        for (int i = 1; i <= m; ++i)
            scanf("%d%d%d", &w[i].a, &w[i].b, &w[i].c);
        sort(w + 1, w + m + 1);
        for (int i = 1; i <= m; ++i)
            if (join(w[i].a, w[i].b))
            {
                join(w[i].a, w[i].b);
                ans += w[i].c;
            }
        printf("%lld\n", ans);
    }
}