#101. 最小费用最大流

内存限制:256 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: StudyingFather

题目描述

这是一道模板题。

给定一个图,每条边有容量和费用,使用每条边的单位流量需要支付特定的费用。给定源点 1 和汇点 n ,求图的最大流和最大流需要支付的最小费用。

输入格式

第一行两个整数 n m ,表示有 n 个点 m 条边。

从第二行开始的之后 m 行,每行四个整数 s_i t_i c_i w_i 表示一条从 s_i t_i 的边,容量为 c_i ,单位流量需要支付的费用为 w_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

数据范围与提示

1 \leq n \leq 400, 0 \leq m \leq 15000, w_i\geq 0 ,保证输入数据、中间结果以及答案在 32 位有符号整数范围内。