利用教材上的标号法求容量网络的最大流。
输入
输入文件包含多个测试数据。每个测试数据描述了一个容量网络及初始可行流,格式为:首先是顶点个数 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 |