P3366题解

Fluffy_fluffy · 2025-06-09 16:26:51 · 题解

前言

需要掌握并查集等前置知识。

思路

最小生成树

最小生成树是指在无向连通图中边权和最小的树。

Kruskal

我们采用Kruskal实现。

如图：

每次选出边权最小的一边，将该边所连接的两点放入一个并查集中。如果两点已经连通（在同一个并查集中）则不进行操作。

证明（贪心）

令树 T_1 和 T_2 是两棵最小生成树则通过它们之间边权最小的边将它们合并为一棵树 T，则 T 也一定是一棵最小生成树。

代码

#include <bits/stdc++.h>
using namespace std;
//#define int long long
struct NODE
{
    int z,x,y;
    bool operator < (const NODE t) const
    {
        return z<t.z;
    }
}; 
int a[5005];
NODE b[200005];
//压缩路径
int find(int x)
{
    if(!a[x]) return x;
    return a[x] = find(a[x]);
}
//加入
void add(int x,int y)
{
    a[find(x)] = find(y);
}
//是否连通
bool isbrother(int x,int y)
{
    return find(x)==find(y);
}
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>b[i].x>>b[i].y>>b[i].z;
    //按边权排序
    sort(b+1,b+1+m);
    int ans = 0;
    for(int i=1;i<=m;i++)
    {
        //不连通就放入同个并查集
        if(!isbrother(b[i].x,b[i].y))
        {
            ans += b[i].z;
            add(b[i].x,b[i].y);
        }
    }
    for(int i=2;i<=n;i++)
    {
        //如果连通的话再压缩路径之后任意两点一定连通
        if(!isbrother(1,i))
        {
            cout<<"orz";
            return 0;
        }
    }
    cout<<ans;
    return 0;
}

后记

部分参考于OI Wiki。