【bzoj1834】[ZJOI2010]network 网络扩容

2014年2月21日3,7030

Description

给定一张有向图,每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求: 1、 在不扩容的情况下,1到N的最大流; 2、 将1到N的最大流增加K所需的最小扩容费用。

Input

输入文件的第一行包含三个整数N,M,K,表示有向图的点数、边数以及所需要增加的流量。 接下来的M行每行包含四个整数u,v,C,W,表示一条从u到v,容量为C,扩容费用为W的边。

Output

输出文件一行包含两个整数,分别表示问题1和问题2的答案。

Sample Input

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

Sample Output

13 19
30%的数据中,N<=100
100%的数据中,N<=1000,M<=5000,K<=10

题解

    第一问很简单,按数据建图,然后一遍最大流算法即可。
    第二问则需要用最小费用最大流算法,主要是建图,那么可以从第一问的残留网络上继续建图,对残留网络上的每一条边建一条容量是∞费用是w的边(反向弧容量为0,费用为-w),然后建一个超级源点,从超级源向1建一条容量为k,费用为0的边,对这个图进行最小费用最大流算法。
    最小费用最大流操作:
    1.首先要对于这道题的图来说,有的边需要花费费用,而有的又不用,而不用扩容的边费用为0,需要扩容的边费用为w,容量无限,这就是本题这样建图的原因。
    2.对于残留网络进行费用最短路SPFA算法,不用扩容的边一定会选费用为0的边,然后记录路径,找最小容量对可行路进行增流,更新ans