#O1106. 最小费用最大流
最小费用最大流
题目描述
给出一个有 个点、 条有向边的网络,源点为 ,汇点为 。每条边有容量 和单位费用 。求该网络的最大流,并在最大流下求最小总费用。
输入格式
第一行四个整数 。
接下来 行,每行四个整数 ,表示从 到 有一条容量为 、单位费用为 的有向边。
输出格式
一行两个整数,依次为最大流与最小总费用,用空格分隔。
样例 #1
样例输入 #1
4 5 1 4
1 2 2 1
1 3 1 2
2 3 1 1
2 4 2 3
3 4 1 4
样例输出 #1
3 14
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 点数 | |
| 边数 | |
| 容量 | |
| 单位费用 |
- 最大流与最小费用均为整数,可用 32 位整型存储。
- 输入保证 ,且 到 存在至少一条路径。