最小割

OI 知识>图论
2k words

最小割

一，相关概念

割：

对于一个网络流图 \(G=(V,E)\)，将所有点划分为两个集合 \(S\) 与 \(T\)，该划分满足：

  1. \(s\in S,\) \(t\in T\)
  2. \(S\cap T=\varnothing,\) \(S\cup T=V\)

称这种点的划分方式为割。

割的容量：

割 \((S,T)\) 的容量为所有从 \(S\) 到 \(T\) 的边的容量之和，即：

\(c(S,T)=\) \(\sum_{u\in S,v\in T}c(u,v)\)

也可以表示为\(c(s,t)\)。

最小割

求一个割 \((S,T)\) 使得 \(c(S,T)\) 最小。

二，最小割求法

最大流最小割

对于一个网络流图，其最大流与最小割相等，即：

\(f(s,t)_{max}=c(s,t)_{min}\)

证明

根据流量守恒特性可以得到 \(\forall u\in V-\{s,t\}\)，\(\sum_{v\in V}f(u,v)-\) \(\sum_{v\in V}f(v,u)=\) \(0\)。

根据流的定义，\(|f|=\) \(\sum_{v\in V}f(s,v)-\) \(\sum_{v\in V}f(v,s)\)。

变形，得：

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

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

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

$ |f| = $ \(\sum_{v \in V}\sum_{u \in S}f(u,v) -\) \(\sum_{v \in V}\sum_{u \in S}f(v,u)\)

$ |f| = $ \(\sum_{v\in V-S}\sum_{u \in S}f(u,v) +\) \(\sum_{v\in S}\sum_{u\in S}f(u,v) -\) \((\sum_{v\in V-S}\sum_{u\in S}f(v,u) +\) \(\sum_{v\in S}\sum_{u\in S}f(v,u))\)

$ |f| = $ \((\sum_{v\in T}\sum_{u \in S}f(u,v) -\) \(\sum_{v\in T}\sum_{u\in S}f(v,u)) +\) \(( \sum_{v\in S}\sum_{u\in S}f(u,v) -\) \(\sum_{v\in S}\sum_{u\in S}f(v,u))\)

即：\(|f|=\) \(f(S,T)+0=\) \(f(S,T)\)。

即任意横跨切割的流量等于网络的流量，又有横跨任意切割的流量不大于切割的容量，可知，网络的流量不大于任意切割的容量，即 \(f(S,T)\leq c(S,T)\)，\(\forall c(S,T)\)。

于是一个网络最大流的值就等于最小切割的容量，这就是最大流最小割定理。

通过最大流最小割定理，我们可以直接通过求最大流来获得最小割。

最小割方案

最小割的可行边

条件：

  1. 满流；

  2. 在残余网络中不连通。

做完最大流后，求残量网络的 SCC。设点 \(x\) 所在的 SCC 为 \(\text{SCC}[x]\)。对于饱和边 \((u,v)\)，若 $[u]$ \(\text{SCC}[ v ]\)，则边 \((u,v)\) 可以在最小割上。

原因

$[u]$ \(\text{SCC}[ v ]\)，则说明 \(u\) 和 \(v\) 在残量网络中不连通，也就相当于跑最大流的时候 \((u,v)\) 满流被删去，又知最小割上的所有边都是满流的，则 \((u,v)\) 可在最小割上。

最小割的必须边

条件：

  1. 满流；

  2. 在残量网络中一端与源点联通，另一端与汇点联通。

做完最大流后，求残量网络的 SCC。设点 \(x\) 所在的 SCC 为 \(\text{SCC}[x]\)。对于饱和边 \((u,v)\)，若 \(\text{SCC}[u]=\) \(\text{SCC}[s]\)，\(\text{SCC}[v]=\) \(\text{SCC}[t]\)，则边 \((u,v)\) 必须在最小割上。

原因

最小割的必须边意味着如果未选中这条边，得到的一定不是最小割，即可以理解为增加容量后可以改变最大流的边，发现对于一条增广路，若其上容量最小的边唯一，那么增大它的容量将会增大整条增广路的流量，于是这条边必须在最小割上，而发现其性质之一是满流，性质之二便是在残量网络中一端与源点联通一端与汇点联通。

最小割点集划分方案

从源点 \(s\) 开始 DFS，每次走残量大于 \(0\) 的边，便能找到 \(S\) 内所有的点了，\(T\) 中的点同理。

1
2
3
4
5
6
7
8
9
10
void dfs(int u)
{
    vis[u]=1;
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(!vis[v]&&edge[i].flow<edge[i].cap)
            dfs(v);
    }
}

最小割任意割边方案

法一：

在残量网络中，DFS 出 \(s\) 能到达的集合 \(S\)，\(S\) 向外连出的所有满流的边即是最小割方案之一。

法二：

每次选取一条满流边 \((u,v)\) DFS 判断在残量网络中能否从 \(v\) 到达 \(u\)，且不经过反向边 \((v,u)\)，若能则 \((u,v)\) 在最小割集中，输出即可。

但注意选取了 \((u,v)\) 后，某些满流边不再是最小割，所以考虑对 \((u,v)\) 退流，后删去边 \((u,v)\) 及其反向边。

最小割最小字典序割边方案

类似于上文法二，但从编号小的满流边开始枚举。

最少割边最小割方案

做完一次最小割后领满流边容量为1，非满流边容量正无穷，再做一次最小割，此时最小割的流量就是选取的边数，任意最小割方案割边都最少。

三，习题

若无特殊情况，所有习题均只给出主函数建图代码，其余代码套用模板

洛谷P3931 一道难题

根节点可看成源点，但发现没有汇点，建立一个超级汇点，在树中找到所有叶子节点，全部以正无穷的容量（保证在最小割中不会被选到）连向超级汇点，求最小割即可，记得开 long long。

code 
1
2
3
4
5
6
7
cin>>n>>s;
t=n+1;
for(ll i=1;i<n;i++)
    cin>>u>>v>>w,addedge(u,v,w);
dfs(s,0);
for(ll i=1;i<=n;i++)
    if(indg[i]==1&&i!=s) addin(i,t,1e18);

洛谷P1345 奶牛的电信

发现求的是使两点不连通的最小割点，考虑割点转割边，于是可以把每个点拆成两个点，一个入点和一个出点，容量为 \(1\)，这样就把点转为了边，其余所有边容量均为正无穷防止被选中。这一思路比较巧妙，其他题目也会用到类似这种点边转化的思想。

code 
1
2
3
4
5
6
7
8
9
cin>>n>>m>>s>>t;
s=s+n;
for(int i=1;i<=n;i++)
    addin(i,i+n,1);
for(int i=1;i<=m;i++)
{
    cin>>u>>v;
    addin(u+n,v,0x3f3f3f3f),addin(v+n,u,0x3f3f3f3f);
}

洛谷P2994 Earthquake Damage G

与上一题类似，割点转割边，注意到没有汇点，对于所有求救的奶牛，可知其与源点的路径上必有割点，对答案有贡献，于是将所有求救奶牛的出点连向超级汇点，之后建立出点和入点间的边，容量为 \(1\)，注意对于求救奶牛，其农场未被摧毁，容量应为正无穷防止被选中。

code 
1
2
3
4
5
6
7
cin>>n>>m>>p,s=n+1,t=n*2+1,c=1;
for(int i=1;i<=m;i++)
    cin>>u>>v,addin(u+n,v,inf),addin(v+n,u,inf);
for(int i=1;i<=p;i++)
    cin>>u,vis[u]=1,addin(u+n,t,inf);
for(int i=1;i<=n;i++)
    vis[i]?addin(i,i+n,inf):addin(i,i+n,1);

洛谷P2057 善意的投票

经典模型之分两个集合。先根据意愿将小朋友分为两派，一派连源点，一派连汇点，对于一对好朋友，连一条正反容量均为1的边即可。

code 
1
2
3
4
5
cin>>n>>m,s=0,t=n+1,c=1;
for(int i=1;i<=n;i++)
    cin>>u,u?addin(s,i,1):addin(i,t,1);
for(int i=1;i<=m;i++)
    cin>>u>>v,addin(u,v,1),addin(v,u,1);
Comments