Skip to content

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了,可以的话,请您参考添加页面,与大家一起分享你的题解!