2327. [图论基础与应用]标号法求网络最大流

利用教材上的标号法求容量网络的最大流。

输入

输入文件包含多个测试数据。每个测试数据描述了一个容量网络及初始可行流,格式为:首先是顶点个数 n 和弧数 m,约定源点为第 0 个顶点,汇点为第 n-1 个顶点;然后是每条弧,格式为 u v c f,分别表示弧的起点、终点、容量和流量。测试数据一直到文件尾。

输出

对每个测试数据,输出各条弧和流量,以及求得的最大流流量,格式如样例输出所示。

样例

标准输入 复制文本
6 10
0 1 8 0
0 2 4 0
1 3 2 0
1 4 2 0
2 1 4 0
2 3 1 0
2 4 4 0
3 4 6 0
3 5 9 0
4 5 7 0
标准输出 复制文本
0->1 : 4
0->2 : 4
1->3 : 2
1->4 : 2
2->1 : 0
2->3 : 1
2->4 : 3
3->4 : 0
3->5 : 3
4->5 : 5
maxFlow : 8
标准输入 复制文本
6 10
0 1 8 2
0 2 4 3
1 3 2 2
1 4 2 2
2 1 4 2
2 3 1 1
2 4 4 0
3 4 6 0
3 5 9 3
4 5 7 2
标准输出 复制文本
0->1 : 4
0->2 : 4
1->3 : 2
1->4 : 2
2->1 : 0
2->3 : 1
2->4 : 3
3->4 : 0
3->5 : 3
4->5 : 5
maxFlow : 8
登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 2
通过 1