最大流/最小割 学习笔记

模板及讲解

最大流问题

  • 容量:一条边$(u,v)$的上限记为$c(u,v)$.(如果边不存在,值为0)
  • 流量:一条边$(u,v)$运送的物品记为$f(u,v)$, $f(u,v)=-f(v, u)$(斜对称性)
  • 流量平衡:$\sum_{(u,v) \in E} f(u,v)=0$

(并且$f(u,v) \leq c(u,v))$

最大流Dinic算法$O(n^2m)$

  • 残量网络:图中每条边上容量和流量之差构成一张新图,称为残量网络(反向弧也要计算)
  • 增广路:增广路是其流量不满,未达到容量上限的一条简单路径
  • 增广路定理(最大流定理):如果残量网络不存在增广路,则当前流为最大流
  • 分层图:以从原点到某点的最短距离分层的图,距离相等的为一层
  • 多路增广:一次BFS进行多次增广
  • 最大可改进量:此次增广最大可以使得增广路的流量增加的量。

Dinic算法的大致思路:
1 先BFS对残量网络进行分层(根据从$S$到点$i$的距离分层,这些和$S$距离相等的点$i$都是一层的)。(初始的图也算一个残量网络)
2 然后再DFS进行多路增广(好处是如果两条不同增广路很长,但是重合了一大半,就不用两次BFS),如果增广到了$T$或者当前最大可改进量(最小残量)等于0就要终止DFS,否则在残量网络上进行增广,必须按照层次来增广,如果路径可以增广,那么路径上的边流量加去最大可改进量(最小残量),反向弧减去最大可改进量(最小残量),因为流量平衡

还可以进行优化,当前弧优化。如果一个点已经增广了一些边,那么这些边在下次DFS的时候不需要再被考虑。

Dinic模板代码见相关代码部分。loj #101
相关学习文章

写时注意:
1 边数组大小。(有一次ins就得乘一次2,最好用vector存)
2 拆点后点数组大小。
3 加边的时候如果无向,则反向弧容量为$c$,否则为$0$

最小割

最小割的流量$f(s,t)$=最大流

在找不到增广路之后,分层了的节点就是 $S$,没分层的点就是 $V-S=T$,即$s-t$割中的两个不相交集合${S, T}$

最大流$flow$是$s-t$最大流,$(S, T)$是$s-t$最小割

最小割的题目:USACO 5.4.3

常见题型:
1、拆点(入点+出点)
Q:求一个图,删去至少几个点,才能使得$S,T$不连通
解:由于是删点,权在点上,所以拆点拆成两个点入点和出点,入点专门负责接受其他节点的入边,出点专门负责连出边
例题:USACO 5.4.3
2、求二分图最大匹配
Q:具体二分图概念及性质
解:弄两个虚节点$s,t$, 使得$s->u$容量为1,$u->v$容量为1,$v->t$容量为1
例题:poj 2536

相关代码
Dinic求最大流,loj #101

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<bits/stdc++.h>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 1000000 + 5, MAXM = 4000000 + 5, INF = 2147483647;
struct data {
int v, cap, flow;//终点,容量,流量
}ed[MAXM * 2];
int n, m, s, t;
vector<int> G[MAXN];
int en, cur[MAXN], d[MAXN], vis[MAXN];//边数,当前弧(用于优化),距离S的距离,访问标记
void ins(int u, int v, int c) {//加双向边
ed[en] = (data){v, c, 0}, G[u].push_back(en++);
ed[en] = (data){u, 0, 0}, G[v].push_back(en++);//反向弧容量为0!不是-c,流量才是守恒的
}
bool bfs() {//求分层图
queue<int> q;
for (int i = 0; i <= n; i++) vis[i] = false;
d[s] = 0, q.push(s), vis[s] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = 0; i < G[u].size(); i++) {
int v = ed[G[u][i]].v, cap = ed[G[u][i]].cap, flow = ed[G[u][i]].flow;
if (!vis[v] && cap > flow) {//没被分层并且可以改进
d[v] = d[u] + 1, vis[v] = true;//分层
q.push(v);
}
}
}
return vis[t];//如果存在增广路则t会被访问
}
int dfs(int u, int a) {//多路增广
if (u == t) return a;//增广到终点
if (a == 0) return 0;//没有可改进量
int retflow = 0;
for (int &i = cur[u]; i < G[u].size(); i++) {
int v = ed[G[u][i]].v, cap = ed[G[u][i]].cap, flow = ed[G[u][i]].flow;
if (d[u] + 1 == d[v]) {//按层次增广
int f = dfs(v, min(a, cap - flow)); //继续增广
if (f > 0) {//能够改进
retflow += f, a -= f, ed[G[u][i]].flow += f, ed[G[u][i] ^ 1].flow -= f;//改进
if (a == 0) break;//优化:没有可改进量时此点应该不再访问
}
}
}
return retflow;
}
int dinic() {//求最大流
int flow = 0;
while (bfs()) {
for (int i = 0; i <= n; i++) cur[i] = 0; //DFS完以后要清空当前弧
flow += dfs(s, INF);
}
return flow;
}
void clean() {
en = 0;
for (int i = 0; i <= n; i++) G[i].clear();
}
void solve() {
clean();
for (int u, v, c, i = 1; i <= m; i++) {
scanf("%d%d%d", &u, &v, &c);
ins(u, v, c);
}
printf("%d\n", dinic());
}
int main() {
scanf("%d%d%d%d", &n, &m, &s, &t), solve();
return 0;
}

------ 本文结束 ------