1449: Maximum flow
题目
题目描述
给定一张源为 $1$，汇为 $n$ 的网络，求 $1$ 到 $n$ 的最大流。
Input
请从 stdin 读入。
输入第一行为两个个正整数 $n, m (2 \leq n, m \leq 200)$。
接下来 $m$ 行，第 $i$ 行为用空格隔开的整数 $u_i, v_i, c_i (1 \leq u_i, v_i \leq n, 1 \leq c_i \leq 200)$，表示一条 $u_i$ 到 $v_i$ 有 $c_i$ 的容量的单向边。
输入可能有重边和自环。
Output
请输出到 stdout 中。
输出一行，包含一个整数，表示最大流的流量。
Sample Input
4 4
1 2 1
2 3 2
1 3 1
3 4 3
3 1
1 2 1
2 3
1 2 1
1 2 1
2 1 1
7 14
1 2 5
1 3 6
1 4 5
2 3 2
2 5 3
3 2 2
3 4 3
3 5 3
3 6 7
4 6 5
5 6 1
6 5 1
5 7 8
6 7 7
Sample Output
2
0
2
14
Constraints
Time Limit: 1s
Memory Limit: 512MB
Hints on implementing a flow algorithm
如果你使用类似邻接链表来存储图，你可能需要存反向边所在的指针，以更新残量网络。你可以这么写：
cpp
struct edge {
edge *next, *reverse;
int to, flow;
};
edge* list_head[N];
void add_edge (int u, int v, int flow) {
edge* uv = new edge (list_head[u], NULL, v, flow);
edge* vu = new edge (list_head[v], NULL, u, 0);
uv->reverse = vu;
vu->reverse = uv;
list_head[u] = uv;
list_head[v] = vu;
}
void traverse(int u) {
for (edge* e = list_head[u]; e != NULL; e = e.next) {
// do something with e
}
}
一个更简洁的写法是这样的。在这种写法里，你无需存储反向边，因为你可以直接对标号异或 1 得到；同时也可以规避 new 动态开内存的开销。
cpp
struct edge {
int next, to, flow;
};
edge e[M * 2]; // back edges
int edge_cnt = 2; // to make reverse(e[x]) = e[x ^ 1], and avoid use number 0
int list_head[N]; // init as 0
void add_edge (int u, int v, int flow) {
e[edge_cnt] = {list_head[u], v, flow};
list_head[u] = edge_cnt++;
e[edge_cnt] = {list_head[v], u, 0};
list_head[v] = edge_cnt++;
}
void traverse(int u) {
for (int cur = list_head[u]; cur != 0; cur = e[cur].next) {
// do something with e[cur]
}
}
如果你使用 std::vector 存图，请注意：vector 在扩容后所有指向元素的迭代器和指针都会失效，因此请使用 std::list 或者存下标的方式来存反向边。
本题可以用最朴素的 Ford-Fulkerson 算法通过。如果你想实现 Dinic 算法，这里推荐实现一种被称为当前弧+多路增广的写法，更简便地实现 dfs 寻找 blocking flow。相比课上讲的删掉走入死路的弧以及饱和弧，这种方法采取如下的标准：
- 如果一条边 $(u, v)$ 访问后，这条边没有消耗掉进入的 $u$ 全部流量，那么就删掉这条边。
实现上就更简单：
- 记录下当前 $u$ 访问到哪条边，一次增广时不会回头访问前面的边。
同时，注意到：
- 如果 dfs 时手上还有流，没有必要立刻退回起点，而是可以把这个点的后继耗尽再回头。
这种方式被称为多路增广。
采用上述的第二种写法，Dinic 的带有多路增广、使用当前弧的 dfs 过程可以写为：
cpp
int cur[N];
int dfs(int x, int flow) {
if (x == sink) return flow;
int used = 0;
for (int &i = cur[x]; i != 0; i = e[i].next) { // i : reference to cur[x]
if (e[i].flow > 0 && level[x] + 1 == level[e[i].to]) {
int ret = dfs(e[i].to, min(e[i].flow, flow - used));
used += ret;
e[i].flow -= ret;
e[i ^ 1].flow += ret;
if (used == flow) break;
}
}
return used;
}
int dinic() {
int ans = 0;
while (make_level()) {
for (int i = 1; i <= n; i++) { // initialize cur[]
cur[i] = list_head[i];
}
ans += dfs(source, INF);
}
return ans;
}
思考题：两种“优化”方法与课上讲的实现有何异同？时间复杂度如何？
Oops! 本题目还没有解答！
助教老师们编题的速度，已经超过了解题的速度！
OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。
如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！