牛客练习赛69 C旅行（最大生成树）

链接：https://ac.nowcoder.com/acm/contest/7329/C
来源：牛客网

最小生成树表示的是 n 个点的路径代价之和最小，该题求 n 个点路径代价之和的最大值，也就是求最大生成树。

证明：转自https://blog.csdn.net/weixin_43872728/article/details/108548041

作者：scimoon

可以发现，对答案有贡献的边肯定是最大生成树上的边，那么可以将这些边先拉出来，每条边至少会被贡献一次

对于当前的一个联通块，找到最小的一条边，那么这个联通块肯定被分成了两个联通块

考虑怎么样才能使答案最优，显然先将一个联通块内选完以后在经过当前边到另一个联通块最优（因为两边的边比当前边要大），可以看出这条边只对答案贡献了一次

这样分治下去就可以得到：将所有生成树上的边的权值加起来就是答案

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
const int inf = 0x3f3f3f3f;

struct node
{
    int u,v;
    ll w;
    bool operator <(const node &a)const
    {
        return w>a.w;
    }
}edge[N];

int father[N];
int n,m;

void init()
{
    for(int i=0;i<=m;i++)
        father[i]=i;
}

int Find(int x)
{
    if(x==father[x])
        return x;
    return father[x]=Find(father[x]);
}

void Union(int x,int y)
{
    int tmpx=Find(x);
    int tmpy=Find(y);
    if(tmpx!=tmpy)
    {
        father[tmpx]=tmpy;
    }
}

ll kruskal()
{
    sort(edge,edge+n);
    init();
    node now;
    ll ans=0;
    for(int i=0;i<n;i++)
    {
        now=edge[i];
        if(Find(now.u)!=Find(now.v))
        {
            Union(now.u,now.v);
            ans+=now.w;
        }
    }
    return ans;
}

int main() {
    scanf("%d%d", &m, &n);
    for(int i = 0; i < n; ++i) {
        scanf("%d%d%lld", &edge[i].u, &edge[i].v, &edge[i].w);
    }
    printf("%lld\n", kruskal());
    return 0;
}