网络扩容
提交数: 4, 通过率: 75%, 平均分: 75
题目描述:
给定一张有向图,每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求:
- 在不扩容的情况下,1到N的最大流;
将1到N的最大流增加K所需的最小扩容费用。
输入格式:
第一行包含三个整数N,M,K,表示有向图的点数、边数以及所需要增加的流量。
接下来的M行每行包含四个整数u,v,C,W,表示一条从u到v,容量为C,扩容费用为W的边。
输出格式:
一行包含两个整数,分别表示问题1和问题2的答案。
样例输入:
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
提示:
30%的数据中,N<=100
100%的数据中,N<=1000,M<=5000,K<=10
时间限制: 1000ms空间限制: 256MB
来源: 浙江省选2010day1t2