Problem
题目描述
如题,给出一个网络图,以及其源点和汇点,每条边已知其最大流量和单位流量费用,求出其网络最大流和在最大流情况下的最小费用。
输入输出格式
输入格式:
第一行包含四个正整数$N,M,S,T$,分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来M行每行包含四个正整数$u_i,v_i,w_i,f_i$,表示第i条有向边从$u_i$出发,到达$v_i$,边权为$w_i$(即该边最大流量为$w_i$),单位流量的费用为$f_i$。
输出格式:
一行,包含两个整数,依次为最大流量和在最大流量情况下的最小费用。
输入输出样例
1 | Input #1 |
1 | Output #1 |
说明
时空限制:1000ms,128MB
最后两个点1200ms
数据规模:
对于30%的数据:$N<=10,M<=10$
对于70%的数据:$N<=1000,M<=1000$
对于100%的数据:$N<=5000,M<=50000$
样例说明:
如图,最优方案如下:
第一条流为4–>3,流量为$20$,费用为$3×20=60$。
第二条流为4–>2–>3,流量为$20$,费用为$(2+1)×20=60$。
第三条流为4–>2–>1–>3,流量为$10$,费用为$(2+9+5)×10=160$。
故最大流量为$50$,在此状况下最小费用为$60+60+160=280$。
故输出$50 280$。
Solution
网络流模板题。
要求在满足最大流情况下的最小费用,可以在最大流的代码上做一些修改。
原本的EK算法是每次BFS只找流量最大的路径路径,现在要求最小费用,可以先找费用最小的,而不是流量最大的。毕竟有路肯定先挑费用少的走嘛。在EK上套一个SPFA就可以了。
如何证明该算法的正确性?
首先要知道,每条流的顺序对最大流的数值不产生影响。那么,先找费用最小的流,可以保证在满足最大流的情况下,找到最小的费用。并且,也不用担心某条流会因为费用太大跑不进去(除非有其他费用更小的流满足了最大流),费用再大也没有∞大,肯定是可以的。
1 |
|
可能开始会有点懵,配上图仔细想一会就能理解。
Data
评测请至洛谷P3381。
注意:LOJ题目和本题略有不同。