2328. [图论基础与应用]用 Dinic 算法求容量网络的最大流

输入

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

输出

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

样例

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