0. 前置芝士
- 令 \(G(f)\) 为流了流 \(f\) 之后的残留网络。
- 定义两个流的加法 \((f+g)(i,j)=f(i,j)+g(i,j)-g(j,i)\)。其中 \(f\) 先流，于是 \(g(j,i)\) 相当于模拟退流的过程。
- 可行流可加性定理：若 \(f\) 为 \(G\) 的可行流，\(g\) 为 \(G(f)\) 的可行流，则 \(f+g\) 是 \(G\) 的可行流，且 \(v(f+g)=v(f)+v(g)\)。
0.1. 最大流最小割定理
对于任意割 \(\mathfrak{G}\)，都可以将点集 \(\mathfrak{V}\) 分成 \(\mathfrak{S,T}\)，它们分别包含源点和汇点。
感性来看，一定有割 \(\mathfrak{G}\) 的净流量 \(=\) 源点输出流量 \(=\) 网络总流量。同时，由于割 \(\mathfrak{G}\) 的净流量一定 \(\le\) 割 \(\mathfrak{G}\) 的容量，我们得出网络总流量 \(\le\) 割 \(\mathfrak{G}\) 的容量。
假设在经过多次增广后，网络上没有增广路了 —— 此时点集 \(\mathfrak{V}\) 自然地分割成 \(\mathfrak{S,T}\)，这两个点集之间的边要么不存在，要么残余流量为零。
那么这些边就是一种割，而且此时割的净流量 \(=\) 割的容量 \(=\) 网络总流量。
下面这张图可以帮助理解网络总流量和割的容量的大小关系。所以此时正好取到最大流和最小割（这指的是容量），故最大流最小割定理得证。另外，这还能证明当没有增广路径时取得最大流。
1. 最大流
1.1. \(\mathtt{EK}\) 算法
1.1.1. 算法流程
首先需要得知 "当无法进行增广时取得最大流"，这个已经在上文 0.1. 最大流最小割定理 中得知。
对于每次增广，跑一遍 \(\rm bfs\) 找能够增广的 边数最短 的路径，然后更新边的残余流量。
1.1.2. 理解
\(lef_i\) 表示这一次增广从源点到点 \(i\) 的流量限制。
对反向边的理解：假设有两条增广路分别经过了正向边 \((u,v)\) 与反向边，实际上就是把流出去的流量的一部分或全部推回点 \(u\)，按另一条路径行进。
初始化时 \(flow\) 表示边的残余流量，正向边为 \(w\)，反向边为零。
1.1.3. 时间复杂度
不明白，是 \(\mathcal O(nm^2)\)。处理数据规模为 \(10^3-10^4\)。
1.1.4. 代码
void addEdge(int u,int v,int w) {
nxt[++cnt]=head[u],to[cnt]=v,flow[cnt]=w,head[u]=cnt;
}
bool bfs() {
while(!q.empty()) q.pop();
rep(i,1,n) vis[i]=0;
q.push(S),vis[S]=1,lef[S]=inf;
while(!q.empty()) {
int u=q.front(); q.pop();
erep(i,u)
if(!vis[v] && flow[i]) {
lef[v]=Min(lef[u],0ll+flow[i]);
q.push(v),pre[v]=i,vis[v]=1;
if(v==T) return 1;
}
}
return 0;
}
void EK() {
while(bfs()) {
int x=T; MaxFlow+=lef[x];
while(x^S) {
flow[pre[x]]-=lef[T],flow[pre[x]^1]+=lef[T];
x=to[pre[x]^1];
}
}
}
int main() {
rep(i,1,m)
u=read(9),v=read(9),w=read(9),
addEdge(u,v,w),addEdge(v,u,0);
EK();
print(MaxFlow,'\n');
return 0;
}
1.2. \(\mathtt{Dinic}\) 算法
1.2.1. 算法流程
其实就是对于 \(\mathtt{EK}\) 算法的一些改进：
- 多路增广：当点 \(u\) 通过 \(\langle u,v\rangle\) 增广之后，还剩下一些流没有用，可以尝试再增广其它的边。
- 有的时候会发生 "绕路" 的情况，我们考虑先用一次 \(\rm bfs\) 将图分层，增广的时候严格按照分层进行。
1.2.2. 一些优化
- 当一个点 \(u\) 到汇点不存在可行流时，将 \(u\) 的层数置为 \(+\infty\)，这样就避免不必要的增广。
- 当前弧优化：完全遍历过的边必然增广完成，可以跳过。注意最后一次增广使用的边不能跳过，每次分层之后重置当前弧。
1.2.3. 代码
\(\text{Dinic}\) 有些时间复杂度证明要求 \(\text{bfs}\) 增广完成，但是提前 return 亲测更快也不知道为什么。这就是玄学复杂度吧。
bool bfs() {
for(int i=1;i<=T;++i)
dep[i]=inf;
while(!q.empty()) q.pop();
q.push(S),arc[S]=head[S],dep[S]=0;
while(!q.empty()) {
int u=q.front(),v; q.pop();
for(int i=head[u];~i;i=e[i].nxt)
if(e[i].w and dep[v=e[i].to]==inf) {
dep[v] = dep[u]+1;
arc[v] = head[v], q.push(v);
if(v==T) return true;
}
}
return false;
}
int dfs(int u,int canFlow) {
if(u==T) return canFlow;
int sumFlow=0,d,v;
for(int i=arc[u];~i;i=e[i].nxt) {
arc[u]=i;
if(e[i].w and dep[v=e[i].to]==dep[u]+1) {
d = dfs(v,min(canFlow,e[i].w));
if(!d) dep[v]=inf;
e[i].w -= d, e[i^1].w += d;
canFlow -= d, sumFlow += d;
if(!canFlow) break;
}
}
return sumFlow;
}
int Dinic() {
int ret=0;
while(bfs()) ret += dfs(S,inf);
return ret;
}
1.2.4. 时间复杂度
戳这，可能还有这个。另外，对于二分图，时间复杂度为 \(\mathcal O(n\sqrt m)\)。普通是 \(\mathcal{O}(n^2m)\) 的，好像加上当前弧优化才是对的。
对于简单容量网络（每一个不是源/汇的点，要么入度为 \(1\)，要么出度为 \(1\)）：\(\mathcal O(nm\sqrt n)\)。
边容量为 \(1\) 的图：\(\mathcal O(\min\{n^{\frac{2}{3}},m^\frac{1}{2}\}\cdot nm)\)。
2. 最小费用最大流
2.1. \(\mathtt{FF}\) 算法 \(+\) \(\text{Dijkstra}\)
2.1.1. 代码
每次增广用 \(\text{Dijkstra}\) 找最短路，然后改变权值。由于不能有负权边，所以定义势函数 \(h(i)\) 等于上次增广的 \(dis_i\)，令这次的边权为 \(h(u)-h(v)+cost(u,v)\)，根据最短路的转移易知边权恒大于等于零。
虽然下面代码没写，但是第一次要跑一次 \(\text{spfa}\)！
void addEdge(int u,int v,int w,int c) {
nxt[++cnt]=head[u],to[cnt]=v,flow[cnt]=w,Cost[cnt]=c,head[u]=cnt;
nxt[++cnt]=head[v],to[cnt]=u,flow[cnt]=0,Cost[cnt]=-c,head[v]=cnt;
}
bool Dijkstra() {
rep(i,1,n) dis[i]=inf;
q.push(make_pair(0,S)); dis[S]=0;
while(!q.empty()) {
Pair t=q.top(); q.pop();
if(dis[t.second]<t.first) continue;
int u=t.second;
erep(i,u)
if(flow[i]>0 && dis[v]>dis[u]+h[u]-h[v]+Cost[i]) {
dis[v]=dis[u]+h[u]-h[v]+Cost[i];
pred[v]=u,pree[v]=i;
q.push(make_pair(dis[v],v));
}
}
return dis[T]^inf;
}
void EK() {
int d,MaxFlow=0,MinCost=0;
while(Dijkstra()) {
rep(i,1,n) h[i]+=dis[i];
// 此时比真实多 h[S]-h[i]，所以将 h[i]+dis[i] 得到真实 dis
d=inf;
for(int i=T;i^S;i=pred[i])
d=Min(d,flow[pree[i]]);
for(int i=T;i^S;i=pred[i])
flow[pree[i]]-=d,flow[pree[i]^1]+=d;
MaxFlow+=d,MinCost+=d*h[T];
}
print(MaxFlow,' '),print(MinCost,'\n');
}
2.2. \(\mathtt{Dinic}\) 算法 \(+\) \(\text{Dijkstra}\)
2.2.1. 代码
\(\bf{Warning}\)：如果 \(c_i\ge 0\) 就可能有零环的情况，此时 dfs() 可能进入死循环。所以需要一个 vis[] 来标记是否访问某点。
bool Dijkstra() {
rep(i,1,n) dis[i]=inf,vis[i]=0;
q.push(make_pair(0,S)); dis[S]=0,arc[S]=head[S];
while(!q.empty()) {
Pair t=q.top(); q.pop();
if(vis[t.second] or dis[t.second]<t.first) continue;
int u=t.second; vis[u]=1;
erep(i,u)
if(flow[i]>0 && dis[v]>dis[u]+h[u]-h[v]+Cost[i]) {
dis[v]=dis[u]+h[u]-h[v]+Cost[i];
arc[v]=head[v],q.push(make_pair(dis[v],v));
}
}
bool ok=(dis[T]^inf);
if(ok) {
rep(i,1,n)
vis[i]=0,
dis[i]=h[i]=h[i]+dis[i];
return 1;
}
return 0;
}
int dfs(int u,int CanFlow) {
vis[u]=1;
if(u==T) return MaxFlow+=CanFlow,CanFlow;
int SumFlow=0,d;
for(int i=arc[u];i;i=nxt[i]) {
int v=to[i]; arc[u]=i;
if(!vis[v] && flow[i]>0 && dis[v]==dis[u]+Cost[i]) {
d=dfs(v,Min(CanFlow,flow[i]));
if(!d) dis[v]=inf;
MinCost+=Cost[i]*d;
flow[i]-=d,flow[i^1]+=d;
SumFlow+=d,CanFlow-=d;
if(!CanFlow) break;
}
}
return SumFlow;
}
void Dinic() {
while(Dijkstra()) dfs(S,inf);
print(MaxFlow,' '),print(MinCost,'\n');
}
3. 如何建图
例 1. \(\text{UVA12125 March of the Penguins}\)
首先可以想到在 \([1,n]\) 枚举汇点，检验最大流是否为企鹅总数。
每个点初始的企鹅数可以由 \(S\rightarrow i\) 的边表示，那跳出的企鹅呢？因为跳到哪个冰块是未知的，所以不妨将 \(i\) 拆成两个点 —— 在入点与出点之间连边权为跳出企鹅数的边。
例 2. \(\text{UVA11082 Matrix Decompressing}\)
这个建图真的好妙啊！假设每一行、列的数字和分别为 \(r_i,c_i\)，将行、列抽象成点，构造边 \(\langle S,i,r_i-m \rangle\)、\(\langle i,T,c_i-n \rangle\)。最后将任意行与列之间连接容量为 \(19\) 的边。
之所以将权值减一是因为网络流跑出的容量包含零，将区间变成 \([0,19]\)，再加一就可以复原。最后如果最大流满流就是有解的。
例 3. 圈地计划
不在同一部分是不好判断的，我们将网格图黑白染色，将黑格的商业区看作白格的工业区，这样就转化成了同一部分的问题！
对于两个相邻的点，连权值为 \(c_{i,j}+c_{i+1,j}\) 的 双向边，\(\text{sum}\) 只增加 \(c_{i,j}+c_{i+1,j}\)。这是因为这条双向边不可能同时删除所有方向。代码：\(\rm Link.\)
另外还有一种复杂度较高的做法：黑白染色之后，对每两个相邻的点建两个虚点 \(g_1,g_2\)，表示同时在左部/右部，分别连 \(\langle S,g_1 \rangle\)、\(\langle g_2,T\rangle\)，再以 \(\text{infty}\) 的权值连接虚点和相邻点。因为枚举了在哪一部，所以复杂度提高。
例 4. 「雅礼集训 2017 Day8」价
先说一下建图：
- 从源点向药 \(i\) 连接权值为 \(\text{infty}-w_i\) 的边。
- 从药向对应的药材连权值为 \(\text{infty}\) 的边。
- 从药材向汇点连权值为 \(\text{infty}\) 的边。
跑一遍最小割，答案就是最小割减去源点连出边的权值。
要想理解这个模型，首先得明确几个性质：
- 最小割不可能割去药与药材之间的边。因为一种药至少对应一种药材，所以割这条边一定不如割掉药材与汇点连边优。
- 割掉源点与药的连边相当于不选此药；割掉汇点与药材的连边相当于选择此药材。第一个比较好理解，对于第二个，考虑求最小割的过程：若药边未割（即选择药），那么药材必须割；若割，则药材可以不割。
- 一定只会割 \(n\) 条边。所有边都带 \(\text{infty}\)，多选一条边一定不优。
- 药和药材数相等。考虑上一条，即 —— 不选的药与选择的药材之和为 \(n\)，而不选的药与选择的药之和也为 \(n\)！所以结论得证。
最后考虑一下为什么定义 "割掉源点与药的连边相当于不选此药" 这样鬼畜的状态。如果我们将源点与药的连边权值改成 \(\text{infty}+w_i\)，即 "割掉源点与药的连边相当于选择此药"，此时药材边可以不割，但实际上我们需要必须不割！
总结：网络流建图时可以设计状态描述 "必须" 与 "可以"。
例 5. \(\text{UVA10735 Euler Circuit}\)
由于有向图存在欧拉回路当且仅当图连通且所有点的入度等于出度。考虑先将无向边定向，然后分配度数。
令 \(d'_i=\) 出度 \(-\) 入度，那么若 \(d'_i\) 为奇数则无解，否则令 \(d_i=d'_i/2\)。对于无向边 \(\langle u,v \rangle\)，若给它定向 \(u\rightarrow v\)，就在网络中连一条 \(u\rightarrow v\)，容量为 \(1\) 的边，表示 \(u\) 可以贡献一个 "度" 给 \(v\)。
对于 \(d_i>0\) 的点，从源点连容量为 \(d_i\) 的边；反之，向汇点连 \(-d_i\) 的边。这样最后检验从源点流出的边是否满流即可（检验汇点也可）。
跑一遍网络流后，当一条边的残余容量为零时，就说明反向。输出的时候记得将边反向遍历，就像这样：
void Print(int u) {
while(!E[u].empty()) {
int v=E[u].back(); E[u].pop_back();
Print(v); printf(" %d",u);
}
}
例 6. \(\text{[JSOI 2009]}\) 游戏
首先一个比较经典的转化是按坐标之和的奇偶性将格点分成两部，这样 \(\text{Alice}\) 和 \(\text{Bob}\) 就只能分别走某一部。
可以证明，当 \(\text{Alice}\) 从一个 不一定 属于最大匹配的点出发，\(\text{Alice}\) 有必胜策略 —— 先假设这个点不属于某个最大匹配 \(G\)，此时 \(\text{Bob}\) 一定 只能 走到一个属于 \(G\) 的点，现在 \(\text{Alice}\) 可以选择走到与当前点匹配的点，下一步，\(\text{Bob}\) 可以走哪些点呢？
看似可以走不属于 \(G\) 的点，但事实上，如果存在这种点，我们就成功找到了一条增广路！这并不符合 \(G\) 是最大匹配的条件。于是 \(\text{Bob}\) 只能走属于 \(G\) 的点，\(\text{Alice}\) 沿用之前的策略，就可以达到必胜的效果。
于是问题转化为，如何求得不一定属于最大匹配的点。最 \(\text{naive}\) 的思路是删去一个点再求最大匹配，不过难道就没有更高效的做法吗？
事实上，先用 \(\text{Dinic}\) 求出一个最大匹配，从一个非匹配点出发，如果到达与自己 同部 的点，那么这些点都是非匹配点。这实际上是 "非匹配 - 匹配 - 非匹配 ..." 的过程，将匹配反向就可以使同部的点状态取反。
具体实现：
- 从源点出发沿 未满流 的边走，回到 \(S\) 部。
- 从汇点出发沿 满流 的边走，回到 \(T\) 部。
注意特判走到源/汇的情况。