BZOJ 1834 [ZJOI2010]network 网络扩容

发布于 2017-05-17  138 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1834

题意:n 个点有向图,m 条边,每条边有一个边权和一个单位扩容费用。两个问题,问题 1 求出最大流,问题 2 求出将最大流增加 K 所需要的最小扩容费用...


当做模板题了,对于问题 1,直接求最大流即可。

问题 2 是需要考虑一下的,我们采用如下做法:方 (tou) 便 (tan) 起见,以 SS,TT 指代超级源汇点,S,T 指代源汇点

对于跑完问题 1 的残量网络,在 SS 和 S 间连一条容量为 K,费用为 0 的边,在原图的每条边间连一条容量为 inf,费用为扩容费用的边,然后跑最小费用流即可。

为什么这么做呢,很显然,因为我们加入了大量容量为 inf 的边,新图中唯一能制约流量的限制就是 SS 和 S 间的边,这样新图的最大流一定是 K,跑费用流一定能跑到它。那么流量合理了,费用呢?我们可以这样的去感性认识一下:跑完最大流后的残量网络中有些边已经跑满了,有些边还可以跑,跑满的边只能通过扩容来继续跑了,扩容是没有限制的所以流量设为 inf,当一条边可以不扩容的时候,由于旧边费用为 0,所以肯定会先跑满剩余的流量再去扩容,这样这么做的正确性就是比较显然的了。

下面给出代码 qwq

 


一个非常弱的准退役OIER