算法进阶课整理
CSDN个人主页:更好的阅读体验
原题链接
题目描述
给定一个包含 $n$ 个点 $m$ 条边的有向图,并给定每条边的容量,边的容量非负。
图中可能存在重边和自环。求从点 $S$ 到点 $T$ 的最小割。
输入格式
第一行包含四个整数 $n,m,S,T$。
接下来 $m$ 行,每行三个整数 $u,v,c$,表示从点 $u$ 到点 $v$ 存在一条有向边,容量为 $c$。
点的编号从 $1$ 到 $n$。
输出格式
输出点 $S$ 到点 $T$ 的最小割。
如果从点 $S$ 无法到达点 $T$ 则输出 $0$。
数据范围
$2 \le n \le 10000$,
$1 \le m \le 100000$,
$0 \le c \le 10000$,
$S \neq T$
思路
最大流最小割定理
对于任意一个流网络 $G=(V,E)$ 都满足:
- 可行流 $f$ 是最大流。
$$\Leftrightarrow$$
- 可行流 $f$ 的残量网络中不存在增广路。
$$\Leftrightarrow$$
- $\exists [\text S,\text T],|f|=c(\text S,\text T)$。
证明:
- $1\Rightarrow 2$:反证法。假设 $f$ 是最大流,且 $G_f$ 存在增广路径。这说明 $G_f$ 存在至少一个流量大于 $0$ 的可行流 $f’$。这样能构造出原网络中另一个可行流 $f+f’$,且 $|f+f’|>|f|$,说明 $f$ 不是最大流,与假设矛盾。
- $2\Rightarrow 3$:构造一个割,使得它在残量网络中不存在增广路径,且 $|f|=c(\text S,\text T)$。定义集合 $\text S$ 为在 $G_f$ 中从 $S$ 出发,沿容量大于 $0$ 的边走能走到的所有的点。由于残量网络中不存在增广路径,所以集合 $\text S$ 中不可能包含 $T$。在定义集合 $\text T = \text V - \text S$,即为构造的合法割。对于正向边 $(u,v)[u\in \text S,v\in \text T]$,由于 $u,v$ 不相通,所以 $f’(u, v)=0$,所以 $f(u,v)=c(u,v)$。对于反向边 $(u,v)[u\in \text T,v\in \text S]$ 同理,$c’(v,u)=0$,即 $f(u,v)=0$。发现原网络中 $\forall (u,v)(u\in\text S,v\in\text T)$,都有 $f(u,v)=c(u,v),f(v,u)=0$。因此 $|f|=f(\text S,\text T)=\sum_{u\in\text S}\sum_{v\in\text T}f(u,v)-\sum_{u\in\text S}\sum_{v\in\text T}f(v,u)=\sum_{u\in\text S}\sum_{v\in\text T}f(u,v)=\sum_{u\in\text S}\sum_{v\in\text T}c(u,v)=c(\text S,\text T)$。
- $3\Rightarrow 1$:由 本文 最小割的推论中已知 $|f|≤c(\text S,\text T)$,且最大流是可行流的一种,所以最大流 $\leq c(\text S,\text T)$。易知 $|f|\leq$ 最大流,而 $|f|=c(\text S,\text T)\geq$ 最大流。即 $|f|\geq$ 最大流。综上得出 $|f|=$ 最大流。已证最大流 $\leq$ 最小割,而最小割又是割的容量的最小值,得出最小割 $\leq c(\text S,\text T)=|f|\leq$ 最大流,即最小割 $\leq$ 最大流,最终得出最大流 = 最小割。
因此要求最小割,只需求原图的最大流即可。
Dinic 算法其实是 EK 算法的一个暴力的优化,EK 算法每次只能搜索一条增广路径,而 Dinic 算法每次都用 DFS 的形式尽可能多的搜索增广路径。
而图中可能存在环,为了保证 DFS 的过程中不会造成死循环,这里可以使用分层图,这样每次都是一层一层往下搜索,就不会出现死循环。
- BFS 建立分层图
- DFS 找出所有能增广的路径
- 累加最大流量
注意: Dinic 算法对于优化非常敏感,如果优化的不好就可能直接 TLE
算法时间复杂度 $O(n^2m)$
AC Code
$\text{C}++$
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10010, M = 200010;
const int INF = 1e9;
int n, m, S, T;
int h[N], e[M], ne[M], f[M], idx;
int d[N], q[N], cur[N];
// d[] 存分层图中每个点的深度
// q[] 手写队列
// cur[] 当前弧优化
inline void add(int a, int b, int c)
{
e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; // 正向边
e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ; // 反向边,用于反悔
}
bool bfs()
{
memset(d, -1, sizeof d); // 记得初始化
int hh = 0, tt = 0;
q[0] = S, d[S] = 0, cur[S] = h[S];
// 将源点加入队列,源点深度为0,初始化源点当前弧为表头
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (d[j] == -1 && f[i]) // 存在增广路才能从这里分层
{
d[j] = d[t] + 1; // 更新深度
cur[j] = h[j]; // 所有点当前弧最开始都是表头
if (j == T) return true; // 如果找到汇点了就说明有增广路
q[ ++ tt] = j;
}
}
}
return false; // 没有增广路
}
int find(int u, int lim) // DFS,u是当前点,lim是u之前的路径能流过的最大值
{
if (u == T) return lim; // 如果已经流到汇点了就返回这个最大值
int flow = 0; // 当前往下流的流量
for (int i = cur[u]; ~i && flow < lim; cur[u] = i, i = ne[i])
// 注意应从当前弧开始遍历,并且每次要更新。没有剩余流量也应该退出
{
int j = e[i];
if (d[j] == d[u] + 1 && f[i])
// 按分层图遍历,防止死循环
{
int t = find(j, min(f[i], lim - flow));
// 找到后面能流的最大值
if (!t) d[j] = -1;
// 如果没有流量那么说明后面没有增广路了,这个点不会用到,将深度设为-1
f[i] -= t, f[i ^ 1] += t, flow += t;
// 当前边减流量,反向边加流量,实际流量加流量
}
}
return flow;
}
int dinic()
{
int r = 0, flow = 0;
while (bfs()) while ((flow = find(S, INF))) r += flow;
// 只要存在增广路就一直DFS,直到DFS出的流量为0
return r;
}
int main()
{
int a, b, c;
memset(h, -1, sizeof h);
scanf("%d%d%d%d", &n, &m, &S, &T);
while (m -- )
{
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
printf("%d\n", dinic());
return 0;
}
最后,如果觉得对您有帮助的话,点个赞再走吧!
咋能这么强/bx