跳转至

最小生成树

定义ψ(｀∇´)ψ

给你一个带权无向图，求它的所有生成树当中权值和最小的一个。

带权无向图 \(G\) 的生成树 \(T\) 定义为包含 \(G\) 的所有节点，由 \(G\) 当中连接它们的 \(n-1\) 条边构成的无向联通子图。

两个定理ψ(｀∇´)ψ

  1. 任意一颗最小生成树一定包含 \(G\) 中最小的边（反证法即可）。

  2. 设一张无向图 \(G=(V,E)\) ，从 \(E\) 中选出 \(k<|V|-1\)条边构成 \(G\) 的一个生成森林，然后再从剩余的 \(|E|-k\) 条边中选出 \(|V|-1-k\) 条边加入森林中，让它成为 \(G\) 的生成树，并且选出的\(\sum w\)最小。

那么，这个生成树一定包含 \(|E|-k\) 条边里面连接生成森林的两个不连通节点的权值最小的边。

证明可以在 zhihu 看看 @ciwei 神仙的专栏。

Kruskal 算法ψ(｀∇´)ψ

基本思想是维护图的最小生成森林。

开始的时候生成森林是空的，每一个节点就是一颗独立的树。

然后用结论 \(2\) 维护森林，利用 dsu 维护联通性。

按照边权升序排个序，然后扫一遍每个边。

如果当前扫到的这条边所连的两个点 \((u,v)\) 已经联通了。那么跳过。

如果不是联通的，根据这一条：

这个生成树一定包含 \(|E|-k\) 条边里面连接生成森林的两个不连通节点的权值最小的边。

把这一条边加入到最小生成树里，顺便合并一下 \((u,v)\)

Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct Edge{ 
    int x,y,z;
    inline bool operator < (const Edge &b)const{ return z<b.z; }
}a[si_m];
struct Dsu{
    int pa[si_n];
    Dsu(){ for(register int i=1;i<=1e2+10;++i) pa[i]=i; }
    inline int root(int x){ if(pa[x]!=x) return pa[x]=root(pa[x]); return pa[x]; }
    inline bool same(int x,int y){ return root(x)==root(y); }
    inline void Union(int x,int y){ int rx=root(x),ry=root(y); if(rx==ry) return; pa[rx]=ry; }
}dsu;

int main(){
    cin>>n>>m;
    for(register int i=1;i<=m;++i){
        cin>>a[i].x>>a[i].y>>a[i].z;
    } sort(a+1,a+1+m); int ans=0;
    for(register int i=1;i<=m;++i){
        if(dsu.same(a[i].x,a[i].y)) continue;   
        dsu.Union(a[i].x,a[i].y),ans+=a[i].z;
    } cout<<ans<<endl;
    return 0;
}

复杂度 \(\text{O}(m \log m)\)。

Prim 算法ψ(｀∇´)ψ

一般用于稠密图。

最开始确定 \(1\) 号节点属于最小生成树。

每一次找到一条权值最小的，且满足它连接的其中一个点 \(u\) 已经被选入最小生成树里，另一个点 \(v\) 则未被选中的边。

具体实现：

维护一个数组 \(dis\) ,如果 \(u\) 没有被选入，那么 \(dis_u\) 就等于 \(u\) 和已经被选中点之间的连边中权值最小的边的权值。

反之 \(dis_u\) 就等于 \(u\) 被选中的时候选出来那条权值最小边的权值。

如何判是否选中呢？

维护一个 \(vis\) 即可。从没有被选中的节点当中选出一个 \(dis\) 最小的，标记它。

扫描和这个被选点的所有出边，更新另外一个端点的 \(dis\) 。

最后生成树的权值和就是 \(\sum\limits^{n}_{i=2} dis_i\)。

Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
inline void Prim(){
    memset(vis,false,sizeof vis),memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    for(register int i=1;i<n;++i){
        int x=0;
        for(register int j=1;j<=n;++j){
            if(!vis[j] && (x==0 || dis[j]<dis[x])) x=j;
        } vis[x]=true;
        for(register int y=1;y<=n;++y) if(!vis[y]) dis[y]=min(dis[y],a[x][y]);
    }
}
int main(){
    cin>>n; memset(a,0x3f,sizeof a);
    for(register int i=1;i<n;++i){
        a[i][i]=0;
        for(register int j=1;j<=n;++j){
            int value; cin>>value;
            a[i][j]=a[j][i]=min(a[i][j],value);
        }
    } Prim(); int ans=0;
    for(register int i=2;i<=n;++i) ans+=dis[i];
    return printf("%d\n",ans),0;
}

复杂度 \(\text{O}(n^2)\)，可以用二叉堆优化到 \(\text{O}(m \log n)\)，但不如直接 Kruskal。

Kruskal 重构树ψ(｀∇´)ψ

一个神奇的科技，因为 \(\texttt{8102ION}\text{归程}\) 这道出了名的题，而被世人所知（

这个东西基于 \(\texttt{Kruskal}\) 实现。

它具有非常多优雅的性质。

做法是在跑 \(\texttt{Kruskal}\) 对于不在同一集合的两个点 \((u,v)\) 连边的时候，我们新建一个节点 \(k\) ，令 \((u,v)\) 分别所在的集合的根 \(r_u,r_v\) 分别作为 \(k\) 的左右儿子。

并且我们把 \(k\) 作为 \(S_u,S_v\) 两个集合合并之后的根。

然后把 \(k\) 的点权置为 \(\delta(u,v)\) 的权值。

跑完 \(\texttt{Kruskal}\) 之后，我们就得到了一颗优美的重构树。

他满足以下性质：

  1. (只考虑新节点)根据构造过程，\(\texttt{Kruskal}\) 重构树是一颗二叉树，并符合二叉堆的性质。
  2. 原来的最小生成树两点间的的最大边权就是 \(\texttt{Kruskal}\) 重构树上两点的 \(\text{Lca}\)的权值。
  3. 重构树中代表原树中的点的节点全是叶子节点，其余节点都代表了一条边的边权。

然后实际上所有新建的点 \(k\) 的含义就是：

如果 \(k\) 的左右子树中的点想要互通，必须要走至少一条边权等于这个点权 \(w_k\) 的边。

有什么用呢？

假设我们一开始的时候从小到大排序，也就是求最小生成树。

那么我们搞出来的重构树上的 \(\text{Lca}(u,v)\) 就代表原图当中 \(u\to v\) 的所有简单路径的边当中的 最大边的最小值。

比如说你原图上 \(1\to 4\) 有两条路径，他们分别是 \(1 \to 2 \to 4,1\to 3 \to 4\)

然后边权是 \(w(1,2)=1,w(1,3)=2,w(3,4)=3,w(2,4)=4\)。

那么第一条路径的最大边是 \(4\) ，第二条的最大边是 \(3\)。

那么 简单路径的边当中的最大边的最小值。这句话的意思就是 \(\min(3,4)=3\)。

推广一下就是 \(\min\limits_{i=1}^{cnt}(\max \{w(uu,vv)\}), (uu,vv \in \forall \delta(u,v))\)

\(cnt\) 是简单路径数。

手元一下：

rebuild.png

这个地方是网上很多博客都写错了的，很明显就是直接抄别人的然后一直抄下去搞得很多都是错的（

好像 OI wiki 这个时候（21/8/22） 也是错的。

然后最大生成树倒过来就行了。

比如重构树的 \(\text{Lca}(u,v)\) 代表的就是最大生成树上 \((u,v)\) 两点之间路径的小边。

然后原图上就是最小边最大。

来一道题理解：

[NOIP2013]货车运输ψ(｀∇´)ψ

A国有 \(n\) 座城市，编号从 \(1\) 到 \(n\)，城市之间有 \(m\) 条双向道路。每一条道路对车辆都有重量限制，简称限重。

现在有 \(q\) 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

就是 最大生成树 中的 \((u,v)\) 之间的路径的最小边。

Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
using namespace std;

const int si_n=1e4+10;
const int si_m=5e4+10;
int n,m,q;

struct Kruskal{
    int u,v,w;
    bool operator < (const Kruskal &b)const{
        return w>b.w;
    }//最大生成树
}e[si_m<<1];
int pa[si_n<<1];
int root(int x){
    if(pa[x]!=x) return pa[x]=root(pa[x]);
    return pa[x];
}

struct Tree{
    int ver,head,Next;
}t[si_m<<1];
int cnt=0,tot=n;//一定注意这里赋值是没用的，要在主函数里读入n之后再赋值！
void add(int u,int v){
    t[++cnt].ver=v,t[cnt].Next=t[u].head;
    t[u].head=cnt;
}
int val[si_n<<1];
bool vis[si_n<<1];
int f[si_n<<1][20],dep[si_n<<1];
void dfs(int i,int fa){
    dep[i]=dep[fa]+1;
    f[i][0]=fa,vis[i]=true;
    for(register int j=1;j<18;++j){
        f[i][j]=f[f[i][j-1]][j-1];
    }
    for(register int j=t[i].head;j;j=t[j].Next){
        int v=t[j].ver;
        if(v==fa) continue;
        dfs(v,i);
    }
}

int lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    for(register int i=19;i>=0;--i){
        if(dep[f[u][i]]>=dep[v]) u=f[u][i];
    }
    if(u==v) return u;
    for(register int i=19;i>=0;--i){
        if(f[u][i]!=f[v][i]){
            u=f[u][i],v=f[v][i];
        }
    }
    return f[u][0];
}
void insert(int u,int v,int w){
    int k=++tot;val[k]=w;
    int ru=root(u),rv=root(v);
    add(k,ru),add(ru,k);
    add(k,rv),add(rv,k);
    pa[k]=pa[ru]=pa[rv]=k;//先加边后合并
}

int main(){
    memset(vis,false,sizeof vis);
    scanf("%d%d",&n,&m);
    tot=n;// qwq
    for(register int i=1;i<=n;++i){
        pa[i]=i;
    }
    for(register int i=1;i<=m;++i){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        e[i]=(Kruskal){u,v,w};
    }
    sort(e+1,e+1+m);
    for(register int i=1;i<=m;++i){
        int ru=root(e[i].u),rv=root(e[i].v);
        if(ru!=rv) insert(e[i].u,e[i].v,e[i].w);
    }
    for(register int i=1;i<=tot;++i){
        if(!vis[i]) dfs(root(i),0);
    }// 防止不连通
    // for(register int i=1;i<=tot;++i){
        // cout<<val[i]<<" ";
    // }
    // puts("");
    scanf("%d",&q);
    while(q--){
        int l,r;
        scanf("%d%d",&l,&r);
        if(root(l)!=root(r)) puts("-1");
        else printf("%d\n",val[lca(l,r)]);
    }
    return 0;
}

然后可以发现这类问题的核心：

若一个点能通过一条路径到达，那么我们走最小（大）生成树上的边也一定能到达该节点。

最后更新: May 9, 2023