#P2604. [ZJOI2010] 网络扩容
[ZJOI2010] 网络扩容
题目描述
给定一张有向图,每条边都有一个容量 和一个扩容费用 。这里扩容费用是指将容量扩大 所需的费用。求:
-
在不扩容的情况下, 到 的最大流;
-
将 到 的最大流增加 所需的最小扩容费用。
输入格式
第一行包含三个整数 ,表示有向图的点数、边数以及所需要增加的流量。
接下来的 行每行包含四个整数 ,表示一条从 到 ,容量为 ,扩容费用为 的边。
输出格式
输出文件一行包含两个整数,分别表示问题 和问题 的答案。
5 8 2
1 2 5 8
2 5 9 9
5 1 6 2
5 1 1 8
1 2 8 7
2 5 4 9
1 2 1 1
1 4 2 1
13 19
提示
数据规模与约定
- 对于 的数据,保证 。
- 对于 的数据,保证 ,,,。