【最小生成树】学习笔记

liruizhou_lihui · 2025-03-30 13:36:03 · 算法·理论

本文中，为了避免歧义，定义：

前置知识

• 树

• 并查集

• 生成树

理论

最小生成树是指边权和最小的生成树，\text{（Minimum Spanning Tree,MST）}。

比如这个图：

它的最小生成树是：

权值之和为 15。

并且没有方案使得其他生成树权值之和比 15 小。

这个树，就是最小生成树。

最小生成树的常见算法有两种：\text{kruskal} 和 \text{prim} 算法。

kruskal

算法实现

每次都会把两个树合并为一个树所以合并次数为 \log n。

综合下来就是 \text{O}(m \log n)。

举例

这里用 OIwiki 的示例来说。

模拟过程：

• 此时剩下两个树，合并 E\leftrightarrow J。

所有边均被处理，\operatorname{Borůvka} 算法结束。

虽然不知道为什么原动图上 E 和 J 没有边。没边不就是最小生成森林了吗，再且如果就是求的是森林还不如每个节点是一个独根树和为 0。

代码

还是 P3366。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN=5000;
const int MAXM=200000;
int n,m;
int u[MAXM+5],v[MAXM+5],w[MAXM+5];
bool used[MAXM+5];
int fa[MAXN+5],Best[MAXN+5];

int findfa(int x)
{
    if(x==fa[x])
    {
        return x;
    }
    return fa[x]=findfa(fa[x]);
}
bool cmp(int x,int y)
{
    if(y==0)
    {
        return 1;
    }
    if(w[x]!=w[y])
    {
        return w[x]<w[y];
    }
    return x<y;
}
void Boruvka()
{
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    int cnt=0,sum=0;
    bool flag=1;
    while(flag)
    {
        flag=0;
        memset(Best,0,sizeof Best);
        for(int i=1;i<=m;i++)
        {
            int U=u[i];
            int V=v[i];
            int W=w[i];
            if(used[i]==1)
            {
                continue;
            }
            int fau=findfa(u[i]);
            int fav=findfa(v[i]);
            if(fau==fav)
            {
                continue;
            }
            if(cmp(i,Best[fau])==1)
            {
                Best[fau]=i;
            }
            if(cmp(i,Best[fav])==1)
            {
                Best[fav]=i;
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(Best[i]!=0&&used[Best[i]]==0)
            {
                flag=1;
                cnt++;
                sum+=w[Best[i]];
                used[Best[i]]=1;
                fa[findfa(u[Best[i]])]=findfa(v[Best[i]]);
            }
        }
    }

    if(cnt==n-1)
    {
        cout<<sum;
    }
    else
    {
        cout<<"orz";
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        cin>>u[i]>>v[i]>>w[i];
    }
    Boruvka();
    return 0;
}

正确性证明

假设 \operatorname{Borůvka} 算法生成的生成树 T 不是最小生成树。根据反证法，存在另一个生成树 T' 满足 \operatorname w(T') < \operatorname w(T)。

考虑 \operatorname{Borůvka} 算法执行过程中第一次选择一条不在 T' 中的边 e 的时刻。

设此时算法处理的树为 x 和 y，且 e 是连接 x 和 y 的最小权边。

由于 T' 是生成树，它必须包含连接 x 和 y 的某条边 f。

那么，有： \operatorname w(e) \le \operatorname w(f)。

否则，会在该步骤中选择 f 而非 e ，与假设矛盾。

将 T' 中的边 f 替换为 e，得到新生成树。

此时：\operatorname w(T'') = \operatorname w(T') - \operatorname w(f) + \operatorname w(e) \le \operatorname w(T')

但 T'' 的总权值不大于 T'，这与 T' 是 \text{MST} 矛盾。因此，原假设不成立，故正确。

一些 \text{MST} 好题

P10928 走廊泼水节

大意就是给你一个最小生成树让你加一些边变成完全图，求完全图的权值最小值。

因为要使新增的权值最小，所以此时对于 u 连通块内到 v 连通块的边边权应该为 w+1，如果更小就会破坏原定的最小生成树。贡献和为 (s_u\times s_v-1)\times(w+1)，s_i 表示 i 联通块的节点数量。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=6000;
const int MAXM=5999;
int n,sum;
int fa[MAXN+5];
int cnt[MAXN+5];
int findfa(int x)
{
    if(fa[x]==x)
    {
        return x;
    }
    return fa[x]=findfa(fa[x]);
}
struct node
{
    int u,v,w;
}e[MAXM+5];
bool cmp(node x,node y)
{
    return x.w<y.w;
}
int t; 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<n;i++)
        {
            cin>>e[i].u>>e[i].v>>e[i].w;
        }
        for(int i=1;i<=n;i++)
        {
            fa[i]=i;
            cnt[i]=1;
        }
        sum=0;
        sort(e+1,e+1+n-1,cmp);
        for(int i=1;i<n;i++)
        {
            int u=e[i].u;
            int v=e[i].v;
            int w=e[i].w;
            int fau=findfa(u);
            int fav=findfa(v);
            sum+=(cnt[fau]*cnt[fav]-1)*(w+1);
            if(cnt[fau]>cnt[fav])
            {
                cnt[fau]+=cnt[fav];
                fa[fav]=fa[u];
            }
            else
            {
                cnt[fav]+=cnt[fau];
                fa[fau]=fa[v];
            }
        }
        cout<<sum<<'\n';
    }
    return 0;
}

P1265 公路修建