重修最小割——无向图与网络

Void_Trailwalker · 2026-07-23 15:27:48 · 算法·理论

本文同步发布至我的blog。

无向图最小割

定义是这样的：将无向图 G 分成两个联通分量 {S,T}，并最小化 \sum_{u\in S,v\in T}d_{(u,v)}。
肯定不能用网络流求。

Stoer-Wagner 算法

首先我们知道对于两点 s,t 和图 G 的一个割 C，如果 s,t 不在同一个联通分量内，那么 C 就是一个 s-t 割。
那么最先想到的肯定是枚举 s,t 求这张图的一个 s-t 割。但是这样太慢了。我们考虑如果这个割不是 s-t 那么 s,t 就在同一个强联通分量内，那么我们可以把它们缩成一个点。
所以很容易想到如下的算法流程：

随便找 s,t，求这张图的 s-t 割。
合并 s,t，如果此时 |V|>1，那么回到步骤 1。
输出所有割中的最小值。

然后我们考虑如果求这张图的 s,t 割。（显然不是最大流）
首先我们维护一个集合 A，初始为空。
定义权值函数 w(A,u)=\sum_{v\in A}d_{(u,v)}。
每次找到 w(A,u) 最大的一个数加入集合，并更新 w。
那么设最后被加入集合的点是 t，其它任意一个点是 s，那么 w(t) 是这张图的一个 s-t 割。

证明

定义节点 u 是活跃的，当且仅当在它加入集合时，设 v 是上一个加入集合的点，对于图 G''=\{V',E'/C\}，u 和 v 不在同一个联通块。
定义集合 A_u 为严格早于 u 加入集合的节点。令 E_u 为 E' 的诱导子图（点集为 A_u\cup\{v\}）的边集。
定义诱导割为 C_v 为 C\cap E_v,w(C_v)=\sum_{(i,j)\in C_v}d_{(i,j)}。
则有对于任何被激活的点 w(A_v,v)\le w(C_v)。
证明：
采用数学归纳法。对于第一个被激活的点 u_0，由定义可知 w(A_{v_0},v_0)=w(C_{v_0})。
对于其它两个被激活的节点 u,v（v 在 u 之前），有 w(A_u,u)=w(A_u-A_v,u)+w(A_v,u)。
已知 w(A_v,u)\le w(A_v,v),w(A_v,v)\le w(C_v)，可得 w(A_u,u)\le w(C_v)+w(A_u-A_v,u)。由于 w(A_u-A_v,u) 对 w(C_u) 有贡献而对 w(C_v) 没有贡献，所以在边权为正的情况下可以导出 w(A_u,u)\le w(A_u) 由于 s 比 t 先加入集合且不在同一联通快，所以 t 是活跃的。可以得出 W(A_t)\le W(C_t)=W(C)。
时间复杂度可以近似看做 O(|V|^3) 的。
但是我好想没找到不能用网络流做的最小割。

核心代码

int Stoer_Wagner(){
    int mincut = 0x3f3f3f3f;
    for(int i=1;i<n;i++){
        int s = 0 , t = 0;
        memset(vis2,0,sizeof(vis2));
        memset(w,0,sizeof(w));
        for(int j=1;j<=n-i+1;j++){
            int now = 0;
            for(int k=1;k<=n;k++){
                if(!vis1[k]&&!vis2[k]&&w[k]>=w[now])now = k;
            }
            s = t , t = now , vis2[now] = 1;
            for(int k=1;k<=n;k++)w[k] += dis[k][now];
        }
        mincut = min(mincut,w[t]);
        vis1[t] = 1;
        for(int j=1;j<=n;j++)if(j!=s)dis[j][s] += dis[j][t] , dis[s][j] += dis[t][j];
    }
    return mincut;
}

网络中的最小割

最大流最小割定理

首先先引入一个引理：对于一个任意的流 f 和割 {S,T}，都有 |f|\le||{S,T}||。直接推式子即可。

|f|=f(s)\\ =\sum_{u\in S}f(u)\\ =\sum_{u\in S}(\sum_{v\in V}f(u,v)-\sum_{v\in V}f(v,u))\\ =\sum_{u\in S}(\sum_{v\in S}f(u,v)+\sum_{v\in T}f(u,v)-\sum_{v\in S}f(v,u)-\sum_{v\in T}f(v,u))\\ =\sum_{u\in S}(\sum_{v\in T}f(u,v)-\sum_{v\in T}f(v,u))+\sum_{u\in S}\sum_{v\in S}f(u,v)-\sum_{u\in S}\sum_{v\in S}f(v,u)\\ =\sum_{u\in S}(\sum_{v\in T}f(u,v)-\sum_{v\in T}f(v,u))\\ \le\sum_{u\in S}\sum_{v\in T}f(u,v)\\ \le\sum_{u\in S}\sum_{v\in T}c(u,v)\\ =||{S,T}||

为了取等，显然第一个不等号需要 \{(u,v)|u\in T,v\in S\} 均为空流，而第二个不等号需要 \{(u,v)|u\in S,v\in T\} 均为满流。
然后我们来证明最大流最小割定理。
我们假设某一轮增广后不存在增广路，记所有能从 s 出发到达的点为集合 S，其余的点为集合 T。那么显然 {S,T} 是原图的一个割且有 ||{S,T}||=\sum_{u\in S}\sum_{v\in T}cf_{(u,v)}=0（不然还存在增广路）。根据容量非负，我们可以得出 \{cf_{(u,v)}|u\in S,v\in T\} 均为 0。
将所有边分两类讨论：

满足我们刚才提到 |f|=||{S,T}|| 的条件，所以最大流等于最小割。所以直接跑最大流即可。

例题

例题 P2762

根据最小割的性质，如果割掉一条边就必须割掉另一条边，那么我们通常在它们中间连接容量为 inf 的边。
在本题中，由于实验必须要用到仪器，所以我们可以将实验和对应仪器连一条这样的边。源点向实验连边，容量为实验的获利。仪器向汇点连边，容量为仪器的价格。割掉表示不选这个实验。
答案即为总共获利减去最小割，输出方案只用输出与源点，汇点直接连接的点即可。

例题 P1344

难点在于如何判断最小割边数。注意到我们将所有边的流量同时乘以一个数，再除回来是不影响答案的，所以我们可以根据这个性质来解题。注意到如果我们对每条边的流量都乘以一个很大的数，然后再加 1，那么最大流 mod 乘上的这个数就是最小割边数。
这是因为我们可以把最大流看做很多流量从源点出发，最后汇聚到汇点，对于两条提前汇聚的增广路，我们只需要割掉汇聚后的一条边即可，而按我们这样建边，它的最大流量正好增加 1。

例题 P4177

考虑割掉中间的边并不影响其它路径。这就对应了租借操作：并不会影响其它的工作。所以我们考虑把中间的边容量改为租借该机器的费用即可。