网络流入门
介绍
网络流
网络流:所有弧上流量的集合f={f(u,v)},称为该容量网络的一个网络流.
网络流图:带权的有向图G=(V,E)，满足以下条件，则称为网络流图(flow network)：
- 仅有一个入度为0的顶点s，称s为源点
- 仅有一个出度为0的顶点t，称t为汇点
- 每条边的权值都为非负数，称为该边的容量，记作
c(i,j)。
弧的流量:通过容量网络G中每条弧<u,v>,上的实际流量(简称流量),记为f(u,v)
性质
- 容量限制：对任意
u,v∈V，f(u,v)≤c(u,v)。 - 反对称性：对任意
u,v∈V，f(u,v) = -f(v,u)。从u到v的流量一定是从v到u的流量的相反值。 - 流守恒性：对任意u，若u不为S或T，一定有
∑f(u,v)=0，(u,v)∈E。即u到相邻节点的流量之和为0，因为流入u的流量和u点流出的流量相等，u点本身不会”制造”和”消耗”流量。
流
可行流: 如果流(流就是指整体的图)满足0<=f(u,v)<=c(u,v)而且满足上文流守恒性,则称此流为可行流.
零流 : 若网络流上每条弧上的流量都为0,则该网络流称为零流.
伪流: 如果一个网络流只满足弧流量限制条件,不满足平衡条件,则这种网络流为伪流,或称为容量可行流.
最大流最小割定理
在一个网络流中，能够从源点到达汇点的最大流量等于如果从网络中移除就能够导致网络流中断的边的集合的最小容量和。
即任何网络中，最大流的值等于最小割的容量。
增广路
如果一个可行流不是最大流，那么当前网络中一定存在一条增广路.
换句话说,f 为最大流的充要条件是在容量网络中不存在增广路
两个概念:
- 前向弧:(方向与链的正方向一致的弧),其集合记为P+,
- 后向弧:(方向与链的正方向相反的弧),其集合记为P-.
设f是一个容量网络G中的一个可行流,P是从Vs到Vt 的一条链,若P满足以下条件:
-
P中所有前向弧都是非饱和弧.
-
P中所有后向弧都是非零弧.
则称P为关于可行流f 的一条增广路.
沿这增广路改进可行流的操作称为增广.
经过思考,这种路为什么称之为增广路呢,是因为可以进行如下操作:每个正向边都尝试正向流通一下,然后每个反向边都尝试减少流量,这也就相当于正向流通了,这也就是下文EK算法要建立反向边的意义所在.
最大流
EK算法(Edmond-Karp)
思想
类似二分图,也是考虑增广路.我们先用bfs随便找一个从s到t的路径,然后很容易求出这个路上的最大流量(其实也就是路上的最小容量).我们先将这个答案加入最后的结果中.然后在统计完这个答案(我们记作inc)之后,为了保证流量不被重复计算,我们将刚才路径上的边的权值都减去inc,同时建立起反向边,每个反向边的容量也是inc.
然后继续bfs(),直到无法找到增广路为止.
我们假设权值都是整数,所以每次答案至少增加1,又由于最大流存在一个客观的上限,所以此算法一定能终止.
这个算法最巧妙的地方就是反向边的加入,使得”反悔”成为可能.这个算法是无后效性的,因为可以这样想:每次都取出了一个路径,然后最后的答案相当于这些路径的叠加,由于反向边的流量的设置,导致不会出现冲突(在边重复的地方经过加减依旧是成立的).
也就是如果我们发现某一条边上分配流量过多，不利于最优方案的推出，我们利用反向边反悔。所以反向边增大的意义就在于正向边的流量减小，也就是“退流”。
复杂度O(n*m^2)还是比较高的.不是很常用,作为理解最大流的思想的例子吧.
模板
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
#include <bits/stdc++.h>
using namespace std;
#define maxn 310
#define inf 0x3f3f3f3f
int n, m, s, t, G[maxn][maxn], pre[maxn], flow[maxn];
int bfs() { // 就是个很普通的bfs,顺带维护flow和pre
for (int i = 1; i <= n; ++i) {
pre[i] = -1;
}
queue<int> q;
q.push(s);
flow[s] = inf;
while (!q.empty()) {
int cur = q.front();
q.pop();
if (cur == t) {
break;
}
for (int i = 1; i <= n; ++i) {
if (G[cur][i] > 0 && pre[i] == -1) {
pre[i] = cur;
flow[i] = min(flow[cur], G[cur][i]);
q.push(i);
}
}
}
if (pre[t] != -1) {
return flow[t];
} else { // 未找到(此时s和t已经不连通)
return -1;
}
}
int EK() {
int inc = bfs();
int maxflow = 0;
while (inc != -1) { // 反复找增广路,直至找不到,就得到了答案
maxflow += inc;
int k = t;
while (k != s) { // 回溯修改刚才找到的增广路
G[pre[k]][k] -= inc;
G[k][pre[k]] += inc;
k = pre[k];
}
inc = bfs();
}
return maxflow;
}
int main() {
while (scanf("%d%d%d%d", &n, &m, &s, &t) != EOF) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
G[i][j] = 0;
}
}
for (int i = 0; i < m; ++i) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
G[u][v] += w;
}
printf("%d\n", EK());
}
return 0;
}
Dinic算法
介绍
Dinic算法还是基于EK算法的思想,即寻找增广路后建立反向边,然后直至参量网络中s和t不再连通之后,就得到了答案.
EK算法的瓶颈是寻找增广路的效率过低,一次bfs只能找到一条路,最坏情况下只能答案增加1.因此改进的方向就是提高增广路的效率,充分利用bfs后的答案.
Dinic算法(神奇的是这个算法居然是EK算法之前发明的),就是采用bfs+dfs交替进行的方式进行增广操作,直至找不到增广路.
add_Edge(int u,int v,int w,int flag):这个是魔改版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
边的结构体还是和链式前向星一样,只是修改了加边的函数
*/
/*关于加入 u->v
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add_Edge(u, v, w, 1);// 加入正向边
add_Edge(v, u, w, 0);// 加入反向边
*/
void add_Edge(int u, int v, int w, int flag) {
edge[cnt].u = u;
edge[cnt].v = v;
// 反向边默认无边权,此处有个优越的地方就是正反的边的编号的二进制只有最后一位相反,所以可以通过异或1的操作变成反向边的编号
edge[cnt].w = flag ? w : 0;
edge[cnt].next = head[u];
head[u] = cnt++;
}
bfs:我们利用bfs构建一个分层图(实际上没这么复杂,就是维护一个数组dis[],dis[v]记录从s到v所经过的路径长度(此处不在乎权值,仅仅看通过几条边) .
dfs(x,limit): x表示当前访问的节点,limit表示截止到这个节点之前的路径上最小的容量.一旦访问到汇点或者Limit为0,就返回limit.但是要注意,此算法只访问当前节点的下一层节点.在访问过程中除了维护EK算法中的正向边反向边和最大流之外,还要即时修改limit,每次都减去inc,一旦limit等于0,则终止访问其他子节点.
这个dfs还要好好思考.
这个算法还有个著名的当前弧优化. 这个是指,如果u向v扩展的路已经被”榨干”了所有流量,那么在之后的dfs过程中如果再次进入u,那么就没必要所有边都遍历了,只需要遍历第一个没被榨干的边即可.也就是cur[u]是u的第一个没被榨干的边的编号.具体解释看代码注释.
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;
#define maxn 10000
#define maxm 100000
#define inf 0x3f3f3f3f
struct Edge {
int u, v, w, next;
} edge[2 * maxm];
int head[maxn];
int cnt;
void add_Edge(int u, int v, int w, int flag) {
edge[cnt].u = u;
edge[cnt].v = v;
// 反向边默认无边权,此处有个优越的地方就是正反的边的编号的二进制只有最后一位相反,所以可以通过异或1的操作变成反向边的编号
edge[cnt].w = flag ? w : 0;
edge[cnt].next = head[u];
head[u] = cnt++;
}
int n, m, s, t, limit[maxn], dis[maxn], cur[maxn];
void init() {
cnt = 0;
for (int i = 1; i <= n; ++i) {
head[i] = -1;
}
}
bool bfs() {
for (int i = 1; i <= n; ++i) {
dis[i] = -1;
}
for (int i = 1; i <= n; i++) // 每次注意复制head
cur[i] = head[i];
dis[s] = 1;
queue<int> q;
q.push(s);
while (!q.empty()) {
int cur = q.front();
q.pop();
for (int i = head[cur]; i + 1; i = edge[i].next) {
int v = edge[i].v;
if (dis[v] < 0 && edge[i].w) {
dis[v] = dis[cur] + 1;
q.push(v);
}
}
}
return dis[t] != -1;
}
int dfs(int x, int limit) {
int inc = 0;
int flow = 0;
if (!limit || x == t)
return limit;
for (int i = cur[x]; i + 1; i = edge[i].next) {
cur[x] = i; // 当前弧优化
int v = edge[i].v;
if (dis[v] == dis[x] + 1 && (inc = dfs(v, min(limit, edge[i].w)))) {
flow += inc;
limit -= inc;
edge[i].w -= inc;
edge[i ^ 1].w += inc;
// 这个非常关键,想了很久才想懂.我们发现limit为0的条件是这样的:在u之后的路径的最大的流量是limit,这个时候的最大流量可能是受u之前的点的影响的所以当前的边在之后还会用到,故break;但是如果最大的流量小于limit,那么就说明沿着这个边走的流量已经被榨干了,所以就前推cur,这里写的确实隐晦了一些.
if (!limit) {
break;
}
}
}
return flow;
}
int Dinic() {
int maxflow = 0;
// bfs();
while (bfs()) {
// printf("bfs loop\n");
maxflow += dfs(s, inf);
}
return maxflow;
}
int main() {
while (scanf("%d%d%d%d", &n, &m, &s, &t) != EOF) {
init();
for (int i = 0; i < m; ++i) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add_Edge(u, v, w, 1);
add_Edge(v, u, w, 0);
}
printf("%d\n", Dinic());
}
return 0;
}
