#102. 最小费用流

内存限制
512 MiB
时间限制
2000 ms
标准输入输出
题目类型
传统
评测方式
文本比较
上传者 admin
原题 loj

题目描述

这是一道模板题。

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

输入格式

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

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

输出格式

一行两个整数,分别表示最大流和最大流需要支付的最小费用。

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

数据范围与提示

,保证输入数据、中间结果以及答案在 32 位有符号整数范围内。