警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「算法」网络流

简介

网络流?好难啊。

由于有各种千奇百怪的网络流题的存在,网络流变得异常复杂。

UPD:

  1. 2018-02-17 21:09:35:Initial Commit
  2. 2018-03-03 22:34:54:Change最小费用最大流 to 费用流,Change代码,Add最小割
  3. 2018-03-04 13:07:48:Change代码
  4. 2018-05-05 23:31:36:Add费用流

没用的概念

  • 网络:带权有向图,记作\(G=(V,E)\)
  • 容量:网络上的边权,边\((u,v)\)的容量记作\(c(u,v)\)
  • 网络流:指为这个有向图分配流并且使得它每条边上的流量都不能超过这条边的容量
  • 流量:网络流上的边权,边\((u,v)\)的流量记作\(f(u,v)\)
  • 可行流满足:
  1. 流量限制:\(0\le f(u,v)\le c(u,v),(u,v)\in E\)

  2. 平衡条件:\(\sum_{v'}f(u,v')-\sum_{v''}f(v'',u)=\left\{\begin{array}{lc}|f|&u=V_s\\0&u\ne V_s,V_t\\-|f|&u=V_t\end{array}\right.\)

    其中\(\sum_{v'}f(u,v')\)是从顶点\(u\)流出的流量之和,\(\sum_{v''}f(v'',u)\)是流入顶点\(u\)的流量之和,\(|f|\)是可行流的总流量,是源点的净流出量,也是汇点的净流入量。

  • 链:前后两两有边项链的点的序列。(准确的说是而不是,之后均使用代替)
  • 前向弧:和链的方向相同。前向弧集合记作\(P^+\)
  • 后向弧:和链的方向相反。后向弧集合记作\(P^-\)
  • 增广路:源点到汇点的一条链,满足前向弧非饱和弧,后向弧非零流弧。

\(0\le f(u,v)<c(u,v),0<f(u,v)\le c(u,v)\)

  • 残留容量剩余流量:还能通过的流量。弧的残留容量剩余流量记作$$。

每条弧对应一个反向残余流量反向剩余流量\(c'(v,u)=-f(u,v)\)

  • 残量网络残余网络剩余网络残留容量剩余流量组成的网络。

:warning: 注意:接下来残留容量剩余容量统一为残留容量残量网络残余网络剩余网络统称残量网络

无聊的概念终于结束了,进入正题

就一个概念而已,一堆名字恶心不恶心

最大流

Ford-FulkersonEdmonds-Karp略。

Dinic

步骤

  1. 初始化
  2. BFS构造层次网络和残量网络。
  3. 如果汇点不在层次网络中算法结束。
  4. 在层次网络中DFS进行增广,然后回到步骤2

优化

  1. BFS只要搜到终点就直接返回true
  2. DFS如果一条边的流量流满了,就不需要再对这条边DFS了,直接返回答案。
  3. DFS如果一个点增广不出流量,那么这次DFS就不要再搜这个点了,再层次图中标记为\(0\)

代码

2018-03-03 22:34:54 Update:

因为STL的指针失效问题,代码被改了。(难怪我不能过BZOJ1711)

只能AC洛谷的模板题可能和洛谷的数据生成器CYaRon有关,说不定生成算法或者输出没有打乱然后不加反向弧/加错反向弧也可以AC?interesting

代码为了兼容long long或高精,typedefFlow_Type,自行更改以适应long long或其它数据。

2018-03-04 13:07:48 Update:

由于原来的代码空间复杂度常数高,于是压了压空间。

该代码用于AcceptedYali 网络流B - Flow Problem或原题HDU3549 - Flow Problem

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;

typedef int Flow_Type;

const Flow_Type INF = 0x3f3f3f3f;
const int N = 31, M = 1003;

struct Edge;

int level[N];
int head[N];

struct Edge {
Flow_Type capacity, flow;
int to, next;
} e[M << 1];

bool levelGraph(int s, int t) {
memset(level, 0, sizeof level);
queue<int> bfs;
bfs.push(s);
level[s] = 1;
while (!bfs.empty()) {
int pos = bfs.front(); bfs.pop();
for (int i = head[pos]; i; i = e[i].next) {
if (e[i].flow < e[i].capacity && !level[e[i].to]) {
level[e[i].to] = level[pos] + 1;
if (e[i].to == t) return true; // 优化一
else bfs.push(e[i].to);
}
}
}
return false;
}

Flow_Type findPath(int s, int t, Flow_Type flow) {
if (s == t) {
return flow;
}
Flow_Type ret = 0;
for (int i = head[s]; ret < flow && i; i = e[i].next) {
if (level[s] + 1 == level[e[i].to] && e[i].flow < e[i].capacity) {
Flow_Type tmp = findPath(e[i].to, t, min(e[i].capacity - e[i].flow, flow));
ret += tmp;
flow -= tmp;
e[i].flow += tmp;
e[i ^ 1].flow -= tmp;
// if (!flow) break; // 优化二
}
}
if (!ret) level[s] = -1; // 优化三
return ret;
}

Flow_Type dinic(int s, int t) {
Flow_Type ans = 0;
while (levelGraph(s, t)) {
ans += findPath(s, t, INF);
}
return ans;
}

int cnt = 1;

void addUndirectedEdge(int from, int to, int capacity) {
// printf("(%d, %d, %d)\n", from, to, capacity);
e[++cnt].to = to; e[cnt].next = head[from]; e[cnt].capacity = capacity; head[from] = cnt;
e[++cnt].to = from; e[cnt].next = head[to]; e[cnt].capacity = capacity; head[to] = cnt;
}

void addDirectedEdge(int from, int to, int capacity) {
// printf("(%d, %d, %d)\n", from, to, capacity);
e[++cnt].to = to; e[cnt].next = head[from]; e[cnt].capacity = capacity; head[from] = cnt;
e[++cnt].to = from; e[cnt].next = head[to]; e[cnt].capacity = capacity; e[cnt].flow = capacity; head[to] = cnt;
}

int t, n, m, a, b, c;

int main() {
scanf("%d", &t);
for (int cn = 1; cn <= t; cn++) {
cnt = 1;
memset(e, 0, sizeof e);
memset(head, 0, sizeof head);
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &a, &b, &c);
addDirectedEdge(a, b, c);
}
printf("Case %d: %d\n", cn, dinic(1, n));
}
}

最小割

根据最大流最小割定理,得出最大流\(=\)最小割。

内容:最大流就是最小割。

定理证明略

费用流

Edmonds-Karp

求最大流的Edmonds-Karp算法的流程是首先bfs找出任意一条增广路,然后增广,直到无法增广。费用流中的Edmonds-Karp算法则是用spfa(别的也行)找出费用最少的一条

步骤

  1. 用SPFA求出费用最少的一条增广路(同时记录路径以便增广)。
  2. 对该路径进行增广,流量 += 终点流量, 费用 += 终点流量 * 源点到汇点的距离(费用)
  3. 如果还能增广,就回到步骤1

代码

该代码用于AcceptedP3381 - 【模板】最小费用最大流

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
#include <bits/stdc++.h>
using namespace std;

struct edge {
int from, to, next, capacity, flow, cost;
} e[100005];

int head[5003], cnt = 1;
int prev[5003];
int flow[5003];

void ek(int s, int t, int& rflow, int& cost) {
int dis[5003];
int vis[5003];
queue<int> bfs;
while (dis[t] != 0x3f3f3f3f) {
memset(prev, 0, sizeof prev);
memset(flow, 0, sizeof flow);
memset(dis, 0x3f, sizeof dis);
memset(vis, 0, sizeof vis);
bfs.push(s);
flow[s] = 0x3f3f3f3f;
dis[s] = 0;
while (!bfs.empty()) {
int pos = bfs.front(); bfs.pop();
vis[pos] = 0;
for (int i = head[pos]; i; i = e[i].next) {
int nx = e[i].to;
if (e[i].flow < e[i].capacity && dis[nx] > dis[pos] + e[i].cost) {
dis[nx] = dis[pos] + e[i].cost;
flow[nx] = min(flow[pos], e[i].capacity - e[i].flow);
prev[nx] = i;
if (!vis[nx]) {
bfs.push(nx);
vis[nx] = 1;
}
}
}
}
for (int i = prev[t]; i; i = prev[e[i].from]) {
e[i].flow += flow[t];
e[i^1].flow -= flow[t];
}
rflow += flow[t];
cost += dis[t] * flow[t];
}
}

void addedge(int x, int y, int z, int w) {
e[++cnt] = (edge){x, y, head[x], z, 0, w}; head[x] = cnt;
e[++cnt] = (edge){y, x, head[y], 0, 0, -w}; head[y] = cnt;
}

int n, m, s, t, x, y, z, w, rflow, cost;

int main() {
scanf("%d%d%d%d", &n, &m, &s, &t);
while (m--) {
scanf("%d%d%d%d", &x, &y, &z, &w);
addedge(x, y, z, w);
}
ek(s, t, rflow, cost);
printf("%d %d", rflow, cost);
return 0;
}