网络流/二分图相关笔记(干货篇)
command_block
2020-05-29 13:54:45
备忘 : [随机化一般图最大匹配](https://www.luogu.com.cn/blog/pks-LOVING/solution-p6113)
请配合 : [网络流/二分图相关笔记(**应用篇**)](https://www.luogu.com.cn/blog/command-block/wang-lao-liu-xiang-guan-bi-ji) 食用
# 0.前面的话
网络流作为一个玄学算法,其题目难度主要在构图上。
至于网络流本身的算法模板,(如果不精细要求复杂度的话)实现起来难度不大。
在此就不多讲模板的实现了,只简单讲讲我对网络流的理解,如果模板部分看不懂建议先找别的文章学习。
本文内容:
主要是模板。
- 网络流模型的构建
- 性质 : 流量守恒,反对称性,流量范围
- 基本结构 : 增广路,反向边,残量网络
- 与线性规划的关系 (咕咕咕)
- 几种常见最大流算法以及复杂度说明
- Ford-Fulkerson
- Edmonds–Karp
- Dinic (包括一些奇怪的优化)
- 关于网络流/二分图的常见模型
- 二分图 : 匹配 , 最小点覆盖 , 独立集 , Hall定理
- 最小路径覆盖
- 闭合子图问题
- 偏序集 : 最小连覆盖 , 最长反链
- 费用流
- EK费用流
- zkw费用流
- 消圈费用流 (咕咕咕)
- 带有负环的费用流
- 费用流与凸性的关系 (咕咕咕)
- 上下界网络流
- 上下界无源汇可行流
- 上下界有源汇可行流
- 上下界有源汇最大流
- 上下界有源汇最小流
- 上下界有源汇费用可行流
- 上下界无源汇费用可行流
- 最小割树及部分证明
# 1.网络流引入
我们这一节的目标就是切掉 [P3376 【模板】网络最大流](https://www.luogu.org/problem/P3376) ,并且要尽量跑得快些。
- ## 网络流问题:
想象一些**有向**的水管,每个水管都有固定的**流量**上限,有源点可以出水,有汇点可以收水,问汇点**单位时间**最多可以收到多少水。
- ## 一些性质$\large{\color{red}*}$
设$f[u,v]$为$u$向$v$流的流量,$c[u,v]$为$u\rightarrow v$的容量限制,$S$为源点,$T$为汇点。
1.$f[u,v]<=c[u,v]$,即每个水管的流量不能超过限制(废话)
2.$f[u,v]=-f[v,u]$,称为**反对称性**
注意,如果$u\rightarrow v$有$x$的流量,那么$f[u,v]=x;\ f[v,u]=-x$
即:$v\rightarrow u$有$-x$的流量,这服从物理上的相对性,也方便了我们分析性质。
(个人认为反对称性是最重要的)
3.$\sum\limits_{v} f[u,v]=0$
即每个点流入和流出的流量相同,简称**流量守恒**(当然源点和汇点不满足)
但是显然,源点流出多少,汇点就流入多少,所以$\sum\limits_{u,v} f[u,v]=0$
**只要满足上述性质,就是个合法的流**,读者可以自行验证一下。
也就是说我们成功地把水流问题抽象成了数学模型。
我们的目标就是让$\sum\limits_{v}f[S,v]$尽量大。
- ## 增广路,残量网络与反向边
我们设$r[u,v]$为**残量网络**,初始时$r[u,v]=c[u,v]$。
几次操作之后$r[u,v]=c[u,v]-f[u,v]$,也就是每条边剩余的容量。
容易发现由于$\sum\limits_{v}f[u,v]=0$,所以$\sum\limits_{v}r[u,v]=\sum\limits_{v}c[u,v]$是不会变化的。
找到残量网络中从$S$到$T$的一条路径,其中的边容量都不为0,这称为一条**增广路**。
(为什么叫做增广路呢,因为水顺着这条路流过去,就可以增加目前流量啊)
然后把最大流加上这些边的最小容量,再把这些边的容量都减去这个值,相当于更新了一次残量网络。
增广一次不只让正向的边流量增加了,还让反向的边流量减少了。
具体来说,假如增广路中有$u\rightarrow v$,我们不仅要让$f[u,v]+=c$,还要让$f[v,u]-=c$以满足流量平衡。
所以$r[u,v]-=c;\ r[v,u]+=c.$
这显得比较魔幻:有些边(剩余)的容量反而变大了?
这有一个绝妙的解释,如果一个流流过本次容量变大的边(即反向边),相当于撤销本次流量,即反悔操作。
**反复寻找增广路,直到找不到为止,此时得到的就是最大流。**$\large{\color{red}*}$
为什么呢?考虑反证法: 假如还有更大的流,那么肯定会有增广路,口胡如下:
我们的流对应的数值是$\sum\limits_{v}f[S,v]$,假如有更大的流,至少会有一个$f[S,v]$会变大。
那么相应地,至少会有一个$f[v,S]$会变小,破坏了守恒性质,为了满足$v$点的流量守恒,有某个或者多个$f[v,u]$会变大,且$u≠S$(不妨只考虑其中一条)
相应地$f[u,v]$会变小,为了满足守恒性质将会有$f[u,v2]$会变大,且$v2≠v,v2≠S$,否则就留成一个圈,流量总和未改变,还是不满足守恒性质。
如此传递下去,假如没有传到$T$就不满足性质,如果传到了$T$就必然是一条增广路。
- ## 算法
设$n$为图的点数,$m$为图的边数。
1.**Ford-Fulkerson**(FF)
非常直觉的算法,直接`dfs`寻找增广路,找到就增广,找不到为止。
这个算法的复杂度是多少?会不会一直能找到增广路而陷入死循环呢?
由于最大流明显有限,每次增广当前流量必然增加,实际上是不会陷入死循环的。
但是`dfs`被出题人随便骗着玩啊,所以复杂度是 $O(m*\text{最大流量})$ 的。
原因就是每次寻找增广路需要 $O(m)$ ,需要找 $O(\text{最大流量})$ 次(基本超时铁了)。
值得注意的是,`FF`算法在二分图上跑的时候,表现很类似匈牙利算法。
虽然这个算法价值不大,还是要多说几句 : 如果某道题目中**最大流量很小**,可以按顺序依次加边,在残量网络上继续增广,会得到 $O(m*\text{最大流量})$ 或者 $O(n*\text{最大流量})$ 的上界,可能比(二分之后)多次建图要快。
2.**Edmonds–Karp**(EK)$\large{\color{red}*}$
在`FF`的基础上,改用`bfs`找增广路(忽略容量为0的边)。
然而,复杂度神奇地变得与值域无关了,变成了$O(nm^2)$
原因 : 使用`bfs`找到的必然是当前含边数最少的一条增广路,找一次需要$O(m)$的时间。
假如要利用反向边的话,必须走到一条边的尽头再往回走,这样一定比当前的最短路要大,所以是不会产生的,这样子我们就不用考虑容量改变的反向边。
每条增广路都有一个瓶颈,而两次增广的瓶颈不可能相同,所以增广路最多 $m$ 条。
而增广路的长度是$[1,n]$,这就证明了EK的复杂度是$O(nm^2)$,实际上只有一个$m$是紧的。
3.**Dinic**$\large{\color{red}*}$
这玩意实现起来难度不大,~~跑起来松松松~~,实战中应用最广。
首先,建立bfs最短路DAG(成为分层操作),然后只走DAG上的边一次`dfs`多路寻找增广路,当找不到的时候再次分层。
如何判断一条边$u\rightarrow v$是否在最短路DAG上:`dis[u]+1==dis[v]`
同EK,同一个分层图中增广路不超过$m$条。
多路增广,就是找到了一条增广路之后不马上停止,剩余的容量试试下一条边,经过下面的优化,一次多路增广复杂度是$O(nm)$。
一次多路增广能够找到当前`DAG`中的所有增广路,迫使增广路变长(边数变多)。
那么要分$n$次层,复杂度就是$O(n^2m)$。有些选手会写单路增广,这样子复杂度是不对的。
优化:
- 当前弧优化
记录每个点已经试**过**了哪些流不出流量的边,下次来就不试了,可以把一次多路增广复杂度严格控制在$O(nm)$内。
证明 : 增广次数为$O(m)$,每次增广最多经过$O(n)$个点,总复杂度为$O(nm)$。
不写这个优化,复杂度是错的,可能会退化成 $O(nm^2)$。
- 点优化
假如从一个点流不出流量,则把该点的`dis`变为$-1$,这样这一次多路增广再也不会来了。
大多数情况下这只能优化常数,但是在某些毒瘤题里面跑的很快。
- 不完全bfs优化
注意到我们bfs到$T$之后就可以停止了,因为后面的路径一定更长。
在随机数据,增广路较短(如匹配问题)里能起到不错的效果,且不会增大常数。
某些需要退流(只涉及部分残量网络以提高效率)的题目,采用这个优化会有更加玄学的加成。
- 交替忽略反向边
比较神奇的优化,目前只由@negiizhao巨神卡到$O(n^{1.5}m)$
首先忽略反向边跑一次**完整的dinic**,此时已经得到了一个近似的较优解。
(注意这里如果每次把$0$边删掉,那么一次忽略反向边的dinic复杂度是$O(nm)$)
再考虑反向边重新跑一次多路增广,最后再次分层。
在随机数据里表现极佳,但是代码量略大。
--------
实战中一般用前三个就够了,复杂度是$O(n^2m)$,实际上远远达不到。
注意,由于边都是成对加入,如果使用邻接链表,则编号连续。
访问反向边时可以直接 `xor 1` ,这样要把开始编号设为 $2$。
如果是 `vector` 写法,只能大力记下反向边的编号。
**Code:**
- 加上{多路增广,当前弧优化,点优化,不完全BFS优化}的`dinic`: (最常用标准版)
下面是邻接链表的写法,需要`vector`写法请查看评测记录。
```cpp
#include<cstdio>
#include<queue>
#define Maxn 10500
#define Maxm 200050
#define INF 1000000000
using namespace std;
int n,m,S,T;
struct Line
{int nxt,t,cap;}l[Maxm];
int tl=1,fir[Maxn],dis[Maxn],cur[Maxn];
void addLine(int f,int t,int cap){
l[++tl]=(Line){fir[f],t,cap};fir[f]=tl;
l[++tl]=(Line){fir[t],f,0};fir[t]=tl;
}
bool bfs()
{
static queue<int> q;
for (int i=1;i<=n;i++)
{cur[i]=fir[i];dis[i]=0;}
q.push(S);dis[S]=1;
while(!q.empty()){
int u=q.front();q.pop();
for (int i=fir[u];i;i=l[i].nxt)
if (l[i].cap&&!dis[l[i].t]){
dis[l[i].t]=dis[u]+1;
if (l[i].t==T){
while(!q.empty())q.pop();
return 1;
}q.push(l[i].t);
}
}return 0;
}
int dfs(int u,int flow)
{
if (u==T)return flow;
int sum=0;
for (int &i=cur[u];i;i=l[i].nxt)
if (dis[l[i].t]==dis[u]+1&&l[i].cap){
int sav=dfs(l[i].t,min(flow,l[i].cap));
if (sav){
l[i].cap-=sav;
l[i^1].cap+=sav;
sum+=sav;flow-=sav;
if (!flow)return sum;
}else dis[l[i].t]=-1;
}
return sum;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&S,&T);
for (int i=1,f,t,cap;i<=m;i++){
scanf("%d%d%d",&f,&t,&cap);
addLine(f,t,cap);
}int ans=0;
while(bfs())ans+=dfs(S,INF);
printf("%d",ans);
return 0;
}
```
[评测记录(vector)](https://www.luogu.com.cn/record/34081669) & [评测记录(邻接链表)](https://www.luogu.com.cn/record/34081724)
图比较稠密的时候`vector`快(耗时可低至邻接链表的`50%~75%`),模板题中数据水且点较多,`vector`建图常数大体现不出优势。
- 加上{多路增广,当前弧优化,点优化,不完全bfs优化,交替忽略反向边}的dinic:
评测记录 : [Loj#127. 最大流 加强版](https://loj.ac/submission/781748) (差一个点就卡过去了……)
# 2.网络流相关经典模型
并不一定需要先完全掌握,可以跳过一部分,先去做题。
- ## 最小割定理
**有源汇割** : 一个边集,删去之后使得源汇不连通,而且其中任意一条边不割,则造成源汇连通(**割是紧的**)
**有源汇最小割** : 一个有向图,边有边权(一般为正),要求割去权值和最小的边集使得源汇不连通。
$\color{blue}\text{定理:}$
$$\text{最小割} = \text{最大流}$$
$\color{blue}\text{证明:}$
- ①最大流 $\leq$ 最小割
首先根据割的定义,所有的流都必然经过割边集中的某一条边,那么流量总和最大就是割边集总和。
- ②最大流 $\geq$ 最小割
考虑我们求出了一个最大流,那么某些边会成为瓶颈,即残量网络上为$0$.
这些边一定分布成为一个割,否则仍然会有增广路。
**最小割的构造** :
跑完最大流之后,从原点选取非$0$边`BFS`,把这些点成为$S$集。
一端在$S$集一端不在的边即为最小割。
- **例题①** : [P4662 [BalticOI 2008]黑手党](https://www.luogu.com.cn/problem/P4662)
这题可以割点而不能割边,我们把点拆成出点入点,中间相连的边为点权即可。
[评测记录](https://www.luogu.com.cn/record/32522922)
- **例题②** : [P4126 [AHOI2009]最小割](https://www.luogu.com.cn/problem/P4126)
**最小割的可行边和必须边**(所有割集的交集和并集)
[题解 P4126 【[AHOI2009]最小割】](https://www.luogu.com.cn/blog/command-block/solution-p4126)
## 图的基本芝士
- **图的匹配** : 选出某些边,使得每两个边没有公共端点。
- **图的独立集** : 选出某些点,使得每两个点没有连边。
- **图的点覆盖** : 选出某些点,每条边都至少有一个端点被选择。
- **闭合子图** : 有向图的子图,满足没有指向子图外的出边。
- **图的路径覆盖** : 在`DAG`上用(边)不相交的简单路径覆盖所有的节点。
## 二分图相关
- **二分图** : 分为两个部分的图(称为左部和右部),同一个部分内没有边。
- **二分图判定** : 充要条件 : 没有奇环。
`dfs`染色判定即可。
- **二分图最大匹配** : 二分图中边最多的匹配(可能有多种方案)。
- [P3386 【模板】二分图匹配](https://www.luogu.org/problem/P3386)
网络流建模方法见第三节。当然也可以用二分图专用算法解决。
另附 : Dinic 算法解决二分图匹配的复杂度上界是 $O(m\sqrt{n})$ 的,一般快于朴素的匈牙利算法。
可见 [Itst : Dinic 二分图匹配 / Hopcroft-Karp 算法 复杂度简单证明](https://www.cnblogs.com/Itst/p/12556871.html)
- **二分图最小点覆盖** :
$\color{blue}\text{定理:}$
$$\text{最小点覆盖}=\text{最大匹配数}$$
**理解&构造** :
- ①二分图角度
首先,最大匹配中的 $a$ 条边是独立的,所以覆盖这些边都必须要 $a$ 个点。
我们称有匹配边相连的点为匹配点,反之为空点。
对于一个二分图的最大匹配,原图的任意一条边都不可能两端都是空点,否则可以在匹配中加入这条边。
所以,我们只考虑匹配边端点的一个子集就能够覆盖所有空点。
①对于每条匹配边,我们选且只选一个端点。
②而一端是匹配点一端是空点的边,必选匹配点。
这两项是不会产生矛盾的,如果一条匹配边两端都被②钦定要选,就造成了 $0-1=1-0$ 的增广路,这与最大匹配相悖。
构造方法就是先根据②钦定,未被钦定的匹配边就随意选取一端。
- ②网络流最小割角度
我们发现,建立二分图匹配模型之后,该图的最小割正好对应着点覆盖 : 对于一条中间的 $\inf$ 边,左右至少割一个端点。
那么通过最小割定理就能自然地引出结论。我们查看那些边被割掉了,也容易构造。(某些优化建边的题目只能这样构造)
例题 : [UVA1194 Machine Schedule](https://www.luogu.com.cn/problem/UVA1194)
- **二分图最大独立集**
$\color{blue}\text{定理:}$
$$\text{最大独立集}=\text{总点数}-\text{最小点覆盖(集合)}$$
**理解&构造** : 先求出点覆盖集合,取补集则得到最大独立集。
独立 : 如果补集之间有连边,则与点覆盖矛盾。
最大 : 如果这个集合更大,则必然要拆掉点覆盖的一部分,这和“最小”点覆盖矛盾。
总而言之,最大独立集和最小点覆盖是对偶问题。这对一般图也是成立的。
- **Hall定理**
二分图完美匹配 : 若两侧点集为 $X,Y$ , 匹配数达到 $\min(|X|,|Y|)$ 称之为完美匹配。
$\color{blue}\text{定理:}$ 不妨设 $|X|\leq |Y|$。
二分图存在完美匹配$\quad\Longleftrightarrow\quad$对于 $1\leq k\leq|X|$，均满足从 $X$ 选出 $k$ 个不同点，连向 $Y$ 的点集大小 $\geq$ $k$
我们称 $X$ 中点集 $S$ 连向 $Y$ 的点集为“邻域”$N(S)$。
**必要性** : 若不满足右侧,则也不满足左侧。
对于某 $k$ 个点,它们连向对面不足 $k $个点,显然无法全部匹配。
**充分性** : 若不满足左侧,假设其满足右侧。
先构造一种最大匹配,此时有未匹配的点存在。
该未匹配点必然有出边,否则违反右侧。如果出边到达的点也不在匹配中,则可以多匹配一条边,矛盾。
若对面的点存在于匹配中,我们找出与其匹配的点,此时我们拥有两个 $X$ 中的点。
根据右侧, $N(S)$ 中会多出一个点和我们已有的点连边。如果这个点未被匹配,则可以匹配。
若已经被匹配,就会在 $X$ 中引入新的点。
如此可以不断增大集合,然而 $X$ 是有限的,必然导出矛盾。
- **推论** : 二分图最大匹配为 $|X|-\max\big(|S|-|N(S)|\big)$
不会用`Hall`定理来推……
可以把式子变为 $\min\big(|X|-|S|+|N(S)|\big)$ 。
如果建立二分图匹配的网络流模型,把 $|X|-|S|$ 看做左侧割掉的点, $N(S)$ 即为右侧割掉的点,取个 $\min$ 就是最小割。
根据最小割定理得证。(似乎也可以得到经典的`Hall`定理?)
- **扩展** : 考虑多重匹配(带容量匹配)的情况,某个点能匹配的次数是$W_u$。
这可以视作将 $u$ 复制 $W_u$ 次的经典二分图。
我们选择 $u$ 复制出的所有点 $S$ ,要满足 $|N(S)|\geq |S|$。
不难发现,由于边是相同的, $S$ 中的任意一个元素 $x$ 都满足 $N(x)=N(S)$。
这样,若 $S$ 满足条件,则 $S$ 的任意子集都满足条件,我们可以把同一个点的复制点集当做整体看待,不妨称作 $T_u$。
选择原图中左侧的点集 $S$ ,设原图中其邻域为 $N(S)$。设 $W(S)=\sum\limits_{u\in S}W_u$
那么在新图中, $S$ 的复制点集大小为 $W(S)$ ,而 $N(S)$ 的复制点集大小为 $W(N(S))$。
这就引出 : 多重匹配有完美匹配的充要条件 : 对于任意的 $S$ ,均满足 $W(S)\geq W(N(S))$
## 闭合子图问题
- **最大权闭合子图** : 点有点权(可正可负),选出点权和最大的闭合子图。
考虑最小割建模。
对于正价点,连源,边权为点权。对应地,负价点连汇,边权为(负)点权。
原图中的有向边保留,边权置为`INF`,此时有:
$$\text{最大权闭合子图}=\text{正点权和}-\text{最小割(构造)}$$
**理解** : 根据结论式子,最小割中割去的边,负权点表示选择,正权点表示不选。
那么我们试图证明 : 在一个割中,割去的负权点和未割的正权点组成的子图$W$与原图的闭合子图对应。
如果$W$不是闭合子图,出边可能指向已经割过的正权点或者未割过的负权点。
如果指向未割过的负权点,则$W$内的流可以通过`INF`边和该点流向汇,与割矛盾。
如果指向已割过的正权点,则$W$内的流相当于“越过”这个割,同样矛盾。
类似地,如果$W$是闭合子图,则$W$对应的流无法流到汇,与割对应。
**构造** : 要求给出闭合子图的方案。
先求出最小割,在闭合子图中的点为 : 未割过的正权点 & 已经割过的负权点。
## 最小路径覆盖
[P2764 最小路径覆盖问题](https://www.luogu.com.cn/problem/P2764) 求所含路径数最少的路径覆盖(点不相交)。
$\color{blue}\text{定理:}$
$$\text{最小路径覆盖}=\text{总点数}-\text{拆点二分图最大匹配}$$
我们采用调整的思想。首先将每个点用单独一个路径覆盖,这是合法的。
每合并两条路径,我们的最终路径数就减小$1$。
我们拆出入点变成二分图,对于图中原有的边,从出点连向入点即可。
某条边被选中,就相当于“串起”了两条已有的路径。(按照最大匹配合并路径即可得知最小路径覆盖)
注意到“单条路径”的限制 : 不能分叉。这跟匹配的“左端点不重复”限制是等价的。
不能多条汇聚,这跟匹配的“右端点不重复”限制是等价的。
所以我们就把最小路径覆盖转化成了二分最大匹配。
[评测记录](https://www.luogu.com.cn/record/33603665)
## 偏序集的最小链覆盖问题
**定义** :
- **偏序集** : 元素之间存在大小关系,允许不可比(无定义)的情况出现。但是比较一定有传递性,且不能互相矛盾。
- **链** : 一个子图,任意两个点都可比。(可以跳过一些中间点,不是图论中的链)
- **反链** : 一个子图,任意两个点都不可比。
能够发现,如果把`DAG`的有向边看做 `>` ,那么一定不会互相矛盾。一般来讲,偏序集通常是以`DAG`的形式给出的。
现在,需要用尽量少且不重的链,覆盖图上的每一个点。
我们先$O(n^3)$求出传递闭包(充分利用传递性)。此时两个点之间的比较可以跳过中间点。
不难发现,新图中的一条连续路径,就对应着原图的一条链。我们求出最小路径覆盖即可。
## 最长反链问题
[P4298 [CTSC2008]祭祀](https://www.luogu.com.cn/problem/P4298) 给出一个部分偏序集,求最长的反链。
$\color{blue}\text{定理:}$
$$\text{最长反链大小}=\text{总点数}-\text{最小链覆盖}$$
可以自行了解 Dilworth 定理。这里只给出下界的构造解。
我们考虑 : 最小链覆盖$\longrightarrow$最小路径覆盖$\longrightarrow$二分图匹配。
这个二分图是由出入点和一系列中间的边组成。
注意到有 $\text{总}-\text{最小链覆盖}=\text{总}-\text{二分图最大匹配}$
求出一个最大独立集 $I$ ,对于一个点 $u$ 如果满足出入点都在 $I$ 内,则将其加入最长反链答案集合 $A$。
先证明 $A$ 是个反链,如果任意两个点之间有边,则违反了独立集的性质。
现在证明 $\text{构造反链大小}\geq\text{总点数}-\text{二分图最大匹配}$
把独立集中的点设为黑点,反之是白点。设原图中的点数为$n$,则二分图中的点数是$2n$。设匹配数(最小连覆盖数)为 $m$。
考虑证明这个反链的大小不低于 $n-m$,结合 Dilworth 定理就得到了正确性。
独立集大小是 $2n-m$ 的,另一方面又等于 $|A|+$满足 “左部点或者右部点**其中一个**属于$I$的$u$的个数”
后者不会超过 $n$ 所以前者就不低于$n-m$。
- **附更为简洁的判定方法** : $u$的入点在$S$集内,且出点不在 $\Leftrightarrow$ $u$在最长反链中。
**证明** : 前文提到,充要条件为 : 出入点均在最大独立集内。
注意到最小点覆盖是最大独立集的补集,这条件相当于 : 出入点均不在最小点覆盖内。
回忆 : 最小点覆盖一定是某条匹配边有闲置边相连的那个端点。
考虑入点,由于其与$S$连通,说明没有流经过入边,也不会造成匹配,自然入点就不是匹配边端点。
考虑出点,一种情况是与世隔绝,自然也不是最小点覆盖。另一种情况是与某条匹配边相邻,但是一定没有额外的闲置边,否则将会能从$S$到达。
回到题目,若需要判定某个点能否存在于最长反链内,直接钦定这个点,删除与其冲突的点,再跑一次即可。
[评测记录](https://www.luogu.com.cn/record/33664680)
# 3.费用流
[P3381 【模板】最小费用最大流](https://www.luogu.com.cn/problem/P3381)
在送水模型的前提下,每条边都增加了一个费用,每一单位的流量通过都需要付出相应的费用。
现在要在流量最大的情况下使得总费用最小。
- **EK**
不难想到,每次找费用最小的增广路进行增广即可。
可以把 `EK` 算法中的 `BFS` 改为 `SPFA` ,直接跑就好了。
复杂度不太对劲,可以卡到指数级,但是正常的出题人一般不会去卡。
```cpp
#include<cstdio>
#include<vector>
#include<queue>
#define Maxn 5100
#define Maxm 100500
#define INF 2147483647
using namespace std;
int n,m,S,T;
struct Line
{int nxt,t,cap,l;}l[Maxm];
int fir[Maxn],tot=1;
inline void addLine(int f,int t,int cap,int cost)
{
l[++tot]=(Line){fir[f],t,cap,cost};
fir[f]=tot;
l[++tot]=(Line){fir[t],f,0,-cost};
fir[t]=tot;
}
int pre[Maxn],lp[Maxn];
int dis[Maxn],flow[Maxn];
bool in[Maxn];
queue<int> t;
int spfa()
{
for (int i=0;i<=n;i++)
{dis[i]=INF;flow[i]=0;}
flow[S]=INF;dis[S]=0;
t.push(S);in[S]=1;
while(!t.empty()){
int u=t.front();
in[u]=0;t.pop();
for (int i=fir[u],v;i;i=l[i].nxt)
if (l[i].cap&&dis[v=l[i].t]>dis[u]+l[i].l){
dis[v]=dis[u]+l[i].l;
flow[v]=min(flow[u],l[i].cap);
lp[v]=i;pre[v]=u;
if (!in[v]){in[v]=1;t.push(v);}
}
}return flow[T];
}
int main()
{
scanf("%d%d%d%d",&n,&m,&S,&T);
for (int i=1,f,t,cap,cost;i<=m;i++){
scanf("%d%d%d%d",&f,&t,&cap,&cost);
addLine(f,t,cap,cost);
}int d,ans=0,cans=0;
while(d=spfa()){
int u=T;
while(u!=S){
int last=pre[u];
l[lp[u]].cap-=d;
l[lp[u]^1].cap+=d;
u=last;
}ans+=d;cans+=d*dis[T];
}printf("%d %d",ans,cans);
return 0;
}
```
[评测记录(邻接链表)](https://www.luogu.com.cn/record/32597994)
[评测记录(vector)](https://www.luogu.com.cn/record/33888712)
(由于未知的原因,在洛谷用`vector`会比邻接链表快很多)
- **zkw**
(起因:`P3705`中差点`TLE`,观察最优解靠前发现写的都是`zkw`)
我们发现前面的`EK`本质上是沿着最短路增广。
仔细思考最短路的定义,设 $D[u]$ 为点 $u$ 的“距离标号”, $l(u,v)$ 为$u,v$ 之间的边权。
则最短路就是需要求解满足如下两个条件的标号。
- ① $D[u]+l(u,v)\geq D[v]$
- ② 对于某个 $v$ ,至少有一个 $u$ 满足 $D[u]+l(u,v)=D[v]$
我们增广之后,某些边的容量变为 $0$ ,也就是说不存在了。这不会破坏①,但是可能破坏②。
`EK`的解决方法是 : 暴力跑一次`SPFA`。这样没有利用到之前网络的信息,十分浪费。
考虑如下的策略 : 先找到目前能到达的集合,称为 $S$ ,反之称为 $T$。
查看目前 $\sum\limits_{u\in S,\ v\in T}D[u]+l(u,v)-D[v]$ 的最小值,然后将 $S$ 中所有的$D$减去这个值。
能够发现我们至少使得有一条边满足了②,$S$集中至少增加一个点.
$S$集内部的点,整体 $D$ 变化而“相对高度”不变,①仍然成立。由于我们取了最小值,所有 $S\rightarrow T$ 的边也仍然满足①。
若仍然无法找到增广路,则再次调整 $D$ 即可。
注意找到增广路时,费用为 $D[T]-D[S]$ 才对。若图含有负权,初始化需要一次`SPFA`。
不难发现,由于也是沿着最短路增广,算法行为和`EK`相同,时间消耗主要在调整 $D$ 上。
最坏情况下,可能需要 $O(n)$ 次 $O(m)$ 的调整才能找到一条新的的增广路,由于`SPFA`复杂度上界也是 $O(nm)$ ,所以两个算法在最差情况下复杂度是相同的。
不难发现,当增广路较短(调整数次即可打通),图较为稠密(打通一条边可以大幅扩展$S$集),费用小(可能会有多条边同时被打通)的时候,`zkw`具有明显的优势。
反之,若增广路较长,费用范围大,图较为稀疏,则`zkw`由于调整的常数较大(可能远大于`SPFA`),跑不过`EK`。(这种情况下同样也存在大量可以把`EK`卡飞的办法)
~~EK的好处就是很多人写,出题人不敢卡,zkw被卡了出题人可以摆手不管。~~
这玩意听起来玄学写起来倒挺短的。
```cpp
#include<cstring>
#include<cstdio>
#include<vector>
#define Maxn 5100
#define INF 1000000000
using namespace std;
struct Line{int t,c,l,b;};
vector<Line> g[Maxn];
void adl(int f,int t,int cap,int len){
g[f].push_back((Line){t,cap,len,g[t].size()});
g[t].push_back((Line){f,0,-len,g[f].size()-1});
}
int n,m,S,T,D[Maxn],ans,cans;
bool vis[Maxn];
int dfs(int u,int lim)
{
vis[u]=1;
if (u==T){ans+=lim;cans-=lim*D[S];return lim;}
for (int i=0,v,sav;i<g[u].size();i++)
if (g[u][i].c&&D[v=g[u][i].t]==D[u]+g[u][i].l&&!vis[v]
&&(sav=dfs(v,min(g[u][i].c,lim)))){
g[u][i].c-=sav;
g[v][g[u][i].b].c+=sav;
return sav;
}
return 0;
}
bool mdf()
{
if (vis[T]==1)return 1;
int z=INF;
for (int u=1;u<=n;u++)if (vis[u])
for (int i=0,v;i<g[u].size();i++)
if (g[u][i].c&&!vis[v=g[u][i].t])
z=min(z,D[u]+g[u][i].l-D[v]);
if (z==INF)return 0;
for (int i=1;i<=n;i++)
if (vis[i])D[i]-=z;
return 1;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&S,&T);
for (int i=1,f,t,cap,cost;i<=m;i++){
scanf("%d%d%d%d",&f,&t,&cap,&cost);
adl(f,t,cap,cost);
}D[S]=-INF;
do{memset(vis,0,sizeof(bool)*(n+5));dfs(S,INF);}while(mdf());
printf("%d %d",ans,cans);
return 0;
}
```
[评测记录](https://www.luogu.com.cn/record/32597994)
图轻度稠密。由于数据随机,增广路应该较短。权值范围较大。`zkw`此时表现得略好于`EK`。
- **原始对偶算法**
在某些题目中，边数 $m$ 会达到 $O(n^2)$ 级别。
此时复杂度上界为 $O(nm)=O(n^3)$ 的 `SPFA` 和 `zkw` 增广方法将会变得十分低效。
此时如果使用朴素的 $\rm Dijstra$ 算法，则可以在 $O(n^2)$ 内完成一次增广了。
但是，残量网络中可能存在负权边，不能直接使用 $\rm Dijstra$。
考虑给每个点设定一个“势能” $h$ ,并让 $u\rightarrow v$ 的边权由 $len$ 改为 $len+h[u]-h[v]$。
由于“势能”的构造方式，不难验证 ： 新图上 $S,T$ 的最短路 $=$ 原图上 $S,T$ 的最短路 $+h[S]-h[T]$。
由于 $h[S]$ 和 $h[t]$ 都是常数，没有本质影响，新图的最短路和原图的最短路是可以对应的。
现在，我们只需要适当地安排每个点的 $h$ ，使得新图的边权均非负，即可使用 $\rm Dij$ 了。
初始时，先使用一次 `SPFA` 求出各个 $dis[u]$ ，然后让 $h[u]=dis[u]$。
根据三角不等式 ：$dis[u]+len\geq dis[v]\Rightarrow len+h[u]-h[v]\geq 0$。 满足新图的边权都非负。
设 $C[u][v]$ 为 $u\rightarrow v$ 的边权。$C'[u][v]$ 为附加势能之后的边权， $dis'[u]$ 为附加势能之后的最短路。
某次增广之后，若加入新边 $v\rightarrow u$ ，则必有 $dis'[u]+C'[u][v]=dis'[v]$ ,即在原来的最短路上。
$\Rightarrow\ dis'[u]+C'[u][v]+h[u]-h[v]=dis'[v]$
$\Rightarrow\ dis'[u]+h[u]-(dis'[v]+h[v])+C'[u][v]=0$
注意到 $C'[u][v]=-C'[v][u]$。
$\Rightarrow\ (dis'[u]+h[u])-(dis'[v]+h[v])-C'[v][u]=0$
可见，若将新的 $h[u]$ 设为 $dis'[u]+h[u]$ ，即可满足新增边权非负。
对于原有的边，则有 $dis'[u]+C'[u][v]\geq dis[v]$
$\Rightarrow\ dis'[u]+C[u][v]+h[u]-h[v]\geq dis[v]$
$\Rightarrow\ (dis'[u]+h[u])-(dis'[v]+h[v])+C[u][v]\geq 0$
同样也满足条件。
不难发现，边修正后的边权总是在减小。
$h$ 每次增加的值不会超过 $n*W$ ，最终的值也就在 "流量$\times n\times$ 边权" 级别的。
[评测记录](https://loj.ac/submission/927918)
- **拆位消圈**
还有一种复杂度比较严格的算法是拆位消圈的算法。
注意到当所有边的容量$\times 2$,则最大流的容量也会$\times 2$,总费用同样会$\times 2$。
我们从二进制的高位向着低位考虑,每次将容量的一位加入,则相当于把所有边的费用$\times 2$,然后加上$0$或者$1$。
现在的问题就是对某些边容量$+1$,求费用流。这样的$+1$操作是$O(m\log C)$次的。
我们可以维护$S$集,看看新加入的边是否“跨越”了当前的割,这样才跑。
复杂度是$O(nm^2\log C)$,实际上松松松~
突然发现要消负环,先留坑。[Link](https://www.luogu.com.cn/paste/m5jxz737)
- **最大费用任意流** & **正费用最大流**
注意到上述费用流算法的共性,每次都会走最长路(注意是最大费用流),使得最长路逐渐缩短。
这个的证明可以模仿普通`
EK`,不难直观感知。
对于最大费用任意流,由于费用一直在减小,当**单次费用**为负时直接不流即可。
正费用最大流指在满足总费用为正的情况下,尽量多流。
由于费用一直在减小,总费用是凸的,当**总费用**为负时直接不流即可。注意最后一次增广可能无法获得增广路中全部流量。
- **带有负环的费用流问题** ： [P7173 【模板】有负圈的费用流](https://www.luogu.com.cn/problem/P7173)
此时我们直接跑 `SPFA` 可能造成死循环.`zkw`的几个基本假设会产生矛盾。
有消负环的办法,不过太玄学了,来日再补罢。
这里介绍一个比较初等的办法,感谢 `myh` 神仙教育Orz。
**需要先学习后面的上下界网络流,才能理解下面的内容。**
首先,对于所有负权边强制满流,可能存在流量不守恒的情况。
我们模仿上下界网络流,记录偏差了多少流量,连源汇进行调整。
这里起到调整作用的“差网络”只能退掉前面的流,以及流上没有被强制的流。
对于前面被强制的流,我们建立反向边来退流,由于退得越少越好,所以费用是负数(毫无违和感)。原图未被强制的的边仍然保留。
形式化地讲,以$(u,v,[f,f],-c),(v,u,[0,f],c)$ 来替换原图中的 $(u,v,[0,f],-c)$。
能够发现,新的网络中不再有负环,所以直接跑最小费用流就可以了。
听起来特别美好,其实会有一些奇怪的`bug`。
- 会破坏图的特殊结构,比如类二分图转化之后就有可能不是二分图了。
- 最大流量可能会变成 $\sum f$ 级别(而非题目中原有的限制),若复杂度依赖于流,可能会导致变慢。
```cpp
#include<algorithm>
#include<cstdio>
#include<queue>
#define MaxN 205
#define pb push_back
using namespace std;
const int INF=2000000000;
struct Line{int t,cap,len;};
vector<Line> g[MaxN];
vector<int> b[MaxN];
void adl(int u,int v,int cap,int len){
b[u].pb(g[v].size());
b[v].pb(g[u].size());
g[u].pb((Line){v,cap,len});
g[v].pb((Line){u,0,-len});
}
int n,m,S,T,flow[MaxN],dis[MaxN],pre[MaxN],id[MaxN];
queue<int> q;
bool in[MaxN];
int spfa()
{
for (int i=1;i<=n+2;i++){flow[i]=0;dis[i]=INF;}
q.push(S);flow[S]=INF;dis[S]=0;
while(!q.empty()){
int u=q.front();
in[u]=0;q.pop();
for (int i=0;i<g[u].size();i++){
if (!g[u][i].cap)continue;
int v=g[u][i].t;
if (dis[v]>dis[u]+g[u][i].len){
dis[v]=dis[u]+g[u][i].len;
flow[v]=min(flow[u],g[u][i].cap);
pre[v]=u;id[v]=i;
if (!in[v]){q.push(v);in[v]=1;}
}
}
}return flow[T];
}
int d[MaxN],ans,ans0;
void adl2(int u,int v,int l,int r,int len)
{d[u]-=l;d[v]+=l;ans+=l*len;if (l<r)adl(u,v,r-l,len);}
void build(){
for (int u=1;u<=n;u++){
if (d[u]>0)adl(S,u,d[u],0);
if (d[u]<0)adl(u,T,-d[u],0);
}
}
int S0,T0;
void EK()
{
int d;
while(d=spfa()){
ans0+=d;
ans+=dis[T]*d;
for (int u=T;u!=S;u=pre[u]){
int las=pre[u];
g[las][id[u]].cap-=d;
g[u][b[las][id[u]]].cap+=d;
}
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&S0,&T0);
adl(T0,S0,INF,0);
for (int i=1,u,v,cap,len;i<=m;i++){
scanf("%d%d%d%d",&u,&v,&cap,&len);
if (len<0){adl2(u,v,cap,cap,len);adl2(v,u,0,cap,-len);}
else adl2(u,v,0,cap,len);
}
S=n+1;T=S+1;build();
EK();ans0=0;
S=S0;T=T0;EK();
printf("%d %d",g[S0][0].cap+ans0,ans);
return 0;
}
```
# 4.上下界网络流
现在每条边不仅有流量上界,还有流量下界。
模板是一个很长的故事。
## 无源汇上下界可行流
[Loj#115. 无源汇有上下界可行流](https://loj.ac/problem/115)
- **无源汇流** : 满足流量平衡即可,大概是几个“涡流”。
设某条边的流量区间是$[L,R]$.
因为每条边都有下界,我们先令每条边流最$L$,称之为“初始流”。
此后,每条边还能在不超过上界的情况下继续流,可以构造一个差网络,令边权为$R-L$,为能额外流的流量。最终在差网络上的流量称作附加流。
我们的初始流不一定满足流平衡,我们就要通过适当地调整差网络使得两个网络的流量加起来平衡。这样我们就构造出了一个可行的循环流。
现在我们就变成了一个差网络上的流问题,只是每个点并不是要求流量守恒,而是要求流量等于给定的数好与初始网络抵消。
我们查看每个点的初始流量代数和 $s$。
如果是正数,则在差网络上需要负数的流。而源点具有负数的流,所以这个点要当源点。
如果是负数,则差网络上需要正数的流。而汇点具有正数的流,所以这个点要当汇点。
多元多汇钦定流量,只需要采用超级源超级汇即可,为了方便我们统一称之为 `SS,TT`。
我们在$\text{(SS,TT)}$之间跑一次普通的有源汇最大流,查看每条源汇边是否流满,都满了则有解。
原网络的流量就相当于初始流+附加流。
[评测记录](https://loj.ac/submission/783208)
## 有源汇上下界可行流
接下来我们要填上源汇,分别称为`S,T`.
可是我们只会求循环流,能不能让这个环经过$(S,T)$呢?
考虑在 $T\rightarrow S$ 建立一条边,权值为 $\text{INF}$,可以理解为“电源内部电流从负极流向正极”。
然后,一个包含这条边的循环流即为有源汇上下界可行流。流量就是该边(可以称之为源汇边或者“电池边”)的流量。
个人觉得还挺好理解的。没有题目所以不放代码了。
## 有源汇上下界最大流
上面我们已经得到了可行流,下一步就令人吃鲸了。
直接在$(S,T)$之间的差网络上跑最大流即可。
一次最大流可以认为是对差网络的调整,而且使得每个点的流量不变,仍然符合条件。
[评测记录](https://loj.ac/submission/783239)
## 有源汇上下界最小流
想不到吧,还有最小流。
仍然是先求出可行流,把电池边删掉,在$(T,S)$之间的差网络上跑最大流,称之为“退流”。
为啥要删掉电池边?不删掉的话,退流的时候能经过这条无穷大边,显然不对劲,可以称之为“短路”。
理性理解就是此时加电池边不是等价操作,去掉之后由于源汇不守恒仍然是合法的。不管电池边里面装了啥,外面也还有相应的环,所以不会丢失信息。
然后把原来的流量减去退掉的流量则得到答案。(一般默认不能从$T$流到$S$,否则按照定义可能出现负数流量?)
[评测记录](https://loj.ac/submission/783248)
另一种方法是二分电池边的容量求解可行流。
## 有源汇最小费用可行流
没什么好说的,直接把前面的最大流换成费用流即可。注意要预先加上初始流的费用。
## 有源汇最小费用可行流
具体流程也差不多,但是无源汇的题目很有可能产生负环,需要用到上面那个带负环的费用流。
# 5.最小割树
[P4897 【模板】最小割树（Gomory-Hu Tree）](https://www.luogu.com.cn/problem/P4897)
定义 $Cut(u,v)$ 为**无向**图中 $u,v$ 之间的最小割大小。
先来讲构造。
对于一张图,先选取任意两点 $u,v$ ,跑一次最小割,将原图分割成 $S,T$ 两个集合。
在 $u,v$ 之间连边,边权为 $Cut(u,v)$。(构建最小割树)
递归求解 $S,T$ 内部的边(注意不要使用残量网络,要原图),直到集合内只有一个点。
不难发现,我们会得到一个树形结构,称作最小割树。( 这样需要求解 $n-1$ 次完整的最大流 )
最小割树满足一个很强的性质 : 两点之间的最小割 **等于** 在最小割树上两点间路径中边的最小权。
一点点来证明。
- **定理1** 任选 $u,v$ 跑一次最小割,将图分成了 $S,T$ 两个集合。
则 $(x\in S,y\in T)\Longrightarrow Cut(x,y)\leq Cut(u,v)$
**证明** : 割断 $u,v$ 的割显然也分隔了 $S,T$ , 所以 $Cut(u,v)$ 是上界。
- **定理2** 任取三点 $a,b,c$ 则 $Cut(a,b),Cut(a,c),Cut(b,c)$ 中最小值至少出现两次。
**证明** : 不妨假设 $Cut(a,b)$ 是最小的,先割开,再讨论 $c$ 在 $S,T$ 的那个集合内。
不妨设其在 $S$ 内,由 {定理1} 得到 $Cut(b,c)\leq Cut(a,b)$ 。
而由$Cut(a,b)$最小的假设则得到 $Cut(b,c)=Cut(a,b)$ ,出现两次。
- **推论1** : $Cut(a,b)\geq \min(Cut(a,c),Cut(b,c))$
若 $Cut(a,b)$ 不是最小值,显然成立,若 $Cut(a,b)$ 是最小值,则一定会出现两次,也会出现在 $\min$ 中。
- **推论2** 对于两点 $(u,v)$ ,有 $Cut(u,v)\geq\min\Big(Cut(u,w_1),Cut(w_1,w_2)...,Cut(w_m,v)\Big)$
多次使用 {推论1} 即可。
- 定理③(最小割树定理) 如上所述。设 $u,v$ 为欲求的两个点, $x,y$ 为路径上的某两个点。
首先,不难得到 $u,v$ 在 $x,y$ 最小割的两侧。由 {定理1} , $Cut(u,v)\leq Cut(x,y)$。
然后根据 {定理2.2} 又能得到 $Cut(u,v)\geq Cut(x,y)$。
这就得到了 $Cut(u,v)=Cut(x,y)$ ,鼓掌!
回到模板题,求出最小割树之后,对于每个询问就是树链 $\min$ 问题了,随手 搜索/倍增 就是。
```cpp
#include<cstdio>
#include<vector>
#include<queue>
#define pb push_back
#define INF 1000000000
#define Maxn 505
#define Maxm 1505
using namespace std;
struct Line{int t,c,b;};
vector<Line> wg[Maxn];
#define g wg
void adl(int f,int t,int cap){
g[f].pb((Line){t,cap,g[t].size()});
g[t].pb((Line){f,cap,g[f].size()-1});
}
int n,m,S,T,dis[Maxn],cur[Maxn];
queue<int> q;
bool bfs()
{
for (int i=1;i<=n;i++){cur[i]=dis[i]=0;}
q.push(S);dis[S]=1;
while(!q.empty()){
int u=q.front();q.pop();
for (int i=0,v;i<g[u].size();i++)
if (g[u][i].c&&!dis[v=g[u][i].t]){
dis[v]=dis[u]+1;
if (v==T){
while(!q.empty())q.pop();
return 1;
}q.push(v);
}
}return 0;
}
int dfs(int u,int flow)
{
if (u==T)return flow;
int sum=0;
for (int &i=cur[u],v;i<g[u].size();i++)
if (dis[v=g[u][i].t]==dis[u]+1&&g[u][i].c){
int sav=dfs(v,min(flow,g[u][i].c));
if (sav){
g[u][i].c-=sav;
g[v][g[u][i].b].c+=sav;
sum+=sav;flow-=sav;
if (!flow)break;
}else dis[v]=-1;
}
return sum;
}
void clear()
{for (int i=1;i<=n;i++)g[i].clear();}
#undef g
struct Data
{int f,t,c;}s[Maxm];
int dinic()
{
clear();
for (int i=1;i<=m;i++)
adl(s[i].f,s[i].t,s[i].c);
int ans=0;
while(bfs())ans+=dfs(S,INF);
return ans;
}
vector<int> g[Maxn],l[Maxn];
void adl2(int f,int t,int len){
g[f].pb(t);l[f].pb(len);
g[t].pb(f);l[t].pb(len);
}
int p[Maxn],sp[Maxn];
void solve(int l,int r)
{
if (l==r)return ;
S=p[l];T=p[r];
int len=dinic();
adl2(S,T,len);
int tn=0,mid=l-1;
for (int i=l;i<=r;i++)
if (dis[p[i]])sp[++tn]=p[i];
else p[++mid]=p[i];
for (int i=1;i<=tn;i++)
p[mid+i]=sp[i];
solve(l,mid);solve(mid+1,r);
}
int qt,cut[Maxn][Maxn],*d;
bool vis[Maxn];
void dfs2(int u,int len)
{
vis[u]=1;d[u]=len;
for (int i=0;i<g[u].size();i++)
if (!vis[g[u][i]])
dfs2(g[u][i],min(len,l[u][i]));
}
int main()
{
scanf("%d%d",&n,&m);n++;
for (int i=1;i<=m;i++){
scanf("%d%d%d",&s[i].f,&s[i].t,&s[i].c);
s[i].f++;s[i].t++;
}for (int i=1;i<=n;i++)p[i]=i;
solve(1,n);
for (int u=1;u<=n;u++){
for (int i=1;i<=n;i++)vis[i]=0;
d=cut[u];dfs2(u,INF);
}scanf("%d",&qt);
for (int i=1,f,t;i<=qt;i++){
scanf("%d%d",&f,&t);
printf("%d\n",cut[f+1][t+1]);
}return 0;
}
```