#B3608. [图论与代数结构 601] 最小费用最大流

[图论与代数结构 601] 最小费用最大流

题目描述

给定 nn 个点,mm 条边,给定每条边的容量和单位流量需要支付的费用,求点 11 到点 nn 的最大流以及此时需要的最小费用。

注意,图可能存在重边。

输入格式

第一行两个整数 nnmm,表示有 nn 个点 mm 条边。

从第二行开始的之后 mm 行,每行四个整数 sis_itit_icic_iwiw_i 表示一条从 sis_itit_i 的边,容量为 cic_i,单位流量需要支付的费用为 wiw_i

输出格式

输出一行两个整数,表示最大流和最小费用。

8 23
2 3 2147483647 1
1 3 1 1
2 4 2147483647 2
1 4 1 2
2 8 2 0
3 5 2147483647 3
1 5 1 3
3 6 2147483647 4
1 6 1 4
3 8 2 0
3 2 2147483647 0
4 6 2147483647 5
1 6 1 5
4 7 2147483647 6
1 7 1 6
4 8 2 0
4 2 2147483647 0
5 8 0 0
5 2 2147483647 0
6 8 0 0
6 2 2147483647 0
7 8 0 0
7 2 2147483647 0

6 24
10 30
1 9 23 2
9 6 29 8
2 8 22 20
7 3 10 16
3 10 18 19
1 2 18 29
9 8 18 15
4 10 5 12
7 5 30 12
7 8 29 7
9 5 20 26
9 4 15 5
9 10 21 6
9 8 15 8
3 4 10 7
3 10 2 5
3 10 26 6
9 3 11 14
6 4 11 7
2 5 1 20
9 5 1 1
6 10 10 17
8 10 29 5
9 4 10 22
5 10 3 14
8 5 16 25
7 10 21 25
1 9 11 16
1 2 14 15
7 9 30 25

57 1594
10 30
7 4 7 19
9 10 6 12
6 4 13 2
3 5 18 21
8 10 12 4
9 4 11 1
2 5 23 2
2 10 2 7
6 5 13 22
8 5 2 10
5 7 12 14
6 5 22 17
5 10 27 23
1 6 1 21
2 7 30 16
4 5 17 12
1 3 27 25
2 7 19 27
1 9 18 25
4 7 30 28
6 10 20 16
1 2 16 21
3 5 26 2
1 9 1 4
1 2 6 7
2 9 25 28
3 8 11 2
2 3 9 14
9 4 16 2
1 7 3 15

47 1821

提示

对于所有数据,保证 1n4001 \le n \le 4000m150000 \le m \le 150000wi23110 \le w_i \le 2 ^ {31} - 1,保证答案在 32 位有符号整数范围内。

本题数据较弱,不存在最小费用最大流的极限情况。

实现时,若使用Bellman-Ford算法可以考虑如下优化:若在某次迭代中所有 π(i)\pi(i) 均保持不变,则不继续迭代。