【模板】最大流Dinic+多路增广+当前弧优化

给定指定的一个有向图,其中有两个特殊的点源S(Sources)和汇T(Sinks),每条边有指定的容量(Capacity),求满足条件的从S到T的最大流(MaxFlow)。

2018-04-08 已更新

在刚学图论的时候,网络流问题真的让我无从下手,后来找时间研究了一下,发现最大流并不难求

由于给定了一个图,那最大流肯定是定下来的。我们想求最大流,就可以按照二分图匹配的思想,先求可行流,然后增广。

所以我们先写一个增广函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int dfs(int now, int res) {
if(now == end) {
return res;
}
for(int edg = first[now]; edg != -1; edg = edge[edg].next) {
if(edge[edg].flow <= 0) continue;
int add = dfs(edge[edg].to, std::min(res, edge[edg].flow));
if(add > 0) {
edge[edg].flow -= add;
return add;
}
}
return 0;
}

long long maxFlow() {
long long res = 0;
while(int add = dfs(start, 0x7fffffff)) {
res += add;
}
return res;
}

但是很明显,在一个图中DFS并不是一个优秀的做法,我们需要优化。

启发式

A*的基础思想告诉我们,尝试启发式搜索也许是个好主意。那我们不仿试一试。

如何启发?

从起点开始BFS一遍,试图把图当成分层图(然而并不是),让DFS一层一层走,一直增广到不能再增广了,就可以结束了。

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
bool setDepth() {
std::queue<int> que;
while(!que.empty()) que.pop();
memset(depth, 0, sizeof(depth));
depth[start] = 1;
que.push(start);
while(!que.empty()) {
int now = que.front();
que.pop();
for(int edg = first[now]; edg != -1; edg = edge[edg].next) {
if(edge[edg].flow > 0 && depth[edge[edg].to] == 0) {
depth[edge[edg].to] = depth[now] + 1;
que.push(edge[edg].to);
}
}
}
return depth[end] != 0;
}

int dfs(int now, int res) {
if(now == end) {
return res;
}
for(int edg = first[now]; edg != -1; edg = edge[edg].next) {
if(depth[edge[edg].to] != depth[now] + 1) continue;
if(edge[edg].flow <= 0) continue;
int add = dfs(edge[edg].to, std::min(res, edge[edg].flow));
if(add > 0) {
edge[edg].flow -= add;
return add;
}
}
return 0;
}

long long maxFlow() {
long long res = 0;
while(setDepth()) {
while(int add = dfs(start, 0x7fffffff)) {
res += add;
}
}
return res;
}

然后我们兴致勃勃地把这篇代码套上主函数交到了OJ上,发现WA了。

![](/images/000.jpg)

为什么会WA?
想一下这样增广真的对吗
当我们遇到下面这种情况的话会怎样:

正常情况下,我们先走S->1->T,再走S->2->T,答案正好是2。但是要是一不小心误入歧途,走了S->1->2->T,接下来就无路可走了。

为了避免这种情况,我们要为自己预备一些后悔药,防止自己走错路:建流量为0的反向边,当正边流量减少时,反边流量增加

1
2
3
4
5
6
7
8
9
10
11
12
13
//链式前向星存图
void addEdge(int from, int to, int flow) {
static int cnt = -1;
edge[++cnt].to = to;
edge[cnt].flow = flow;
edge[cnt].next = first[from];
first[from] = cnt;
edge[++cnt].to = from;
edge[cnt].flow = 0;
edge[cnt].next = first[to];
first[to] = cnt;
return;
}

我们以 0index 来存边,那么一个边的反向边就是它自己 ^ 1,也方便了我们找反向边。

所以DFS时的更新流量操作也要改一下

1
2
3
4
5
6
int add = dfs(edge[edg].to, std::min(res, edge[edg].flow));
if(add > 0) {
edge[edg].flow -= add;
edge[edg ^ 1].flow += add;
return add;
}

好的,现在我们整理一下,交到洛谷上

AC!

交到LOJ上喜加一!

emmmmmmm……

为什么会这样呢

然后我翻了下红书,发现maxFlow函数并不是我这么写的,而是这样

1
2
3
4
5
6
7
long long maxFlow() {
long long res = 0;
while(setDepth()) {
res += dfs(start, 0x7fffffff);
}
return res;
}

比我的少了一个while循环。我试图理解了一下,这样写确实比我的写法要更优,所以换上这个再交一发:

AC!

请注意,红书上DFS也与我不一样,这一点在文章结尾已更新

最后放上整份代码:

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
94
95
96
97
//LOJ101,未封装
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>

const int MAX_NODE_NUM = 100;
const int MAX_EDGE_NUM = 5000;

struct Edge {
int to;
int flow;
int next;
} edge[(MAX_EDGE_NUM << 1) + 1];

int first[MAX_NODE_NUM + 1];
int depth[MAX_NODE_NUM + 1];
int start;
int end;

void addEdge(const int, const int, const int);
long long maxFlow();

int main() {
//init
memset(first, -1, sizeof(first));
int noden;
int edgen;
scanf("%d%d%d%d", &noden, &edgen, &start, &end);
while(edgen--) {
int from, to, flow;
scanf("%d%d%d", &from, &to, &flow);
addEdge(from, to, flow);
}
///init

//solve&print
printf("%lld\n", maxFlow());
///solve&print
}

inline void addEdge(const int from, const int to, const int flow) {
static int cnt = -1;
edge[++cnt].to = to;
edge[cnt].flow = flow;
edge[cnt].next = first[from];
first[from] = cnt;
edge[++cnt].to = from;
edge[cnt].flow = 0;
edge[cnt].next = first[to];
first[to] = cnt;
return;
}

bool setDepth() {
std::queue<int> que;
while(!que.empty()) que.pop();
memset(depth, 0, sizeof(depth));
depth[start] = 1;
que.push(start);
while(!que.empty()) {
int now = que.front();
que.pop();
for(int edg = first[now]; edg != -1; edg = edge[edg].next) {
if(edge[edg].flow > 0 && depth[edge[edg].to] == 0) {
depth[edge[edg].to] = depth[now] + 1;
que.push(edge[edg].to);
}
}
}
return depth[end] != 0;
}

int dfs(int now, int res) {
if(now == end) {
return res;
}
for(int edg = first[now]; edg != -1; edg = edge[edg].next) {
if(depth[edge[edg].to] != depth[now] + 1) continue;
if(edge[edg].flow <= 0) continue;
int add = dfs(edge[edg].to, std::min(res, edge[edg].flow));
if(add > 0) {
edge[edg].flow -= add;
edge[edg ^ 1].flow += add;
return add;
}
}
return 0;
}

long long maxFlow() {
long long res = 0;
while(setDepth()) {
res += dfs(start, 0x7fffffff);
}
return res;
}

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
//luogu最大流,半封装
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using std::queue;
using std::min;

const int MAX_NODE_NUM = 10000;
const int MAX_EDGE_NUM = 100000;

class NetworkFlow {
private:
bool MakeDepth();
int Dfs(int, int);
int cnt;
int start;
int end;
int first[MAX_NODE_NUM + 1];
int depth[MAX_NODE_NUM + 1];
int to[MAX_EDGE_NUM << 1 | 1];
int flow[MAX_EDGE_NUM << 1 | 1];
int next[MAX_EDGE_NUM << 1 | 1];
public:
NetworkFlow(int = 0, int = 0);
void AddEdge(int, int, int);
int MaxFlow();
};

NetworkFlow::NetworkFlow(int from, int to)
: start(from), end(to), cnt(-1) {
memset(first, -1, sizeof(first));
memset(NetworkFlow::to, 0, sizeof(NetworkFlow::to));
memset(flow, 0, sizeof(flow));
memset(next, -1, sizeof(next));
return;
}

void NetworkFlow::AddEdge(int from, int to, int flow) {
++cnt;
NetworkFlow::to[cnt] = to;
NetworkFlow::flow[cnt] = flow;
next[cnt] = first[from];
first[from] = cnt;
++cnt;
NetworkFlow::to[cnt] = from;
NetworkFlow::flow[cnt] = 0;
next[cnt] = first[to];
first[to] = cnt;
return;
}

bool NetworkFlow::MakeDepth() {
queue<int> que;
memset(depth, 0, sizeof(depth));
depth[start] = 1;
que.push(start);
while(!que.empty()) {
int now = que.front();
que.pop();
for(int nxt = first[now]; nxt != -1; nxt = next[nxt]) {
if(flow[nxt] > 0 && depth[to[nxt]] == 0) {
depth[to[nxt]] = depth[now] + 1;
que.push(to[nxt]);
}
}
}
if(depth[end] == 0) {
return 0;
}
return 1;
}

int NetworkFlow::Dfs(int now, int res) {
if(now == end) return res;
for(int nxt = first[now]; nxt != -1; nxt = next[nxt]) {
if(depth[to[nxt]] != depth[now] + 1) continue;
if(flow[nxt] <= 0) continue;
int d = Dfs(to[nxt], min(res, flow[nxt]));
if(d > 0) {
flow[nxt] -= d;
flow[nxt ^ 1] += d;
return d;
}
}
return 0;
}

int NetworkFlow::MaxFlow() {
int res = 0;
while(MakeDepth()) {
res += Dfs(start, 0x7fffffff));
}
return res;
}

int main() {
int edgen;
int noden;
int start, end;
scanf("%d%d%d%d", &noden, &edgen, &start, &end);
NetworkFlow group(start, end);
int from, to, flow;
for(int i = 1; i <= edgen; ++i) {
scanf("%d%d%d", &from, &to, &flow);
group.AddEdge(from, to, flow);
}
printf("%d\n", group.MaxFlow());
return 0;
}

2018-04-08更新

日后发现我虽然过了LOJ的普通模板,但是这并不是一个标准写法。正确的写法应该是多路增广,就是一次DFS增广很多条路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int dfs(int now, int flow) {
if(now == end) {
return flow;
}
int res = 0;//update
for(int edg = first[now]; edg != -1; edg = edge[edg].next) {
if(depth[edge[edg].to] != depth[now] + 1) continue;
if(edge[edg].flow <= 0) continue;
int add = dfs(edge[edg].to, std::min(flow, edge[edg].flow));
//if(add > 0) {//update
edge[edg].flow -= add;
edge[edg ^ 1].flow += add;
flow -= add;//update
res += add;//update
if(flow == 0) break;//update
//}//update
}
if(res == 0) depth[now] = 0;//update
//在此感谢igronemyk大佬为我指出这个卡了我很久的地方
//这个是用来保证多路增广复杂度的
return res;//update
}

有变化的地方已经用注释标上了update,应该很好理解,就不赘述了。

在向群里的dalao请教后得知还有个当前弧优化。
加上这个后成功更强地A掉了这道题

当前弧,故名思义,就是当前的弧。

当前弧优化,就是记录一下这个结点目前走到哪条边了,下次走的时候直接从这条边开始走就行。

能砍掉很多无用的时间

代码:https://paste.ubuntu.com/p/NFXYs9sdyr/