bzoj 1834: [ZJOI2010]network 网络扩容 最大流+费用流

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


做这个水题的过程可真是曲折

一开始我问camouflager跑个费用为0的费用流和跑个dinic差多少

讨论了一会结果是zkw费用流比较好

我就去看zkw费用流

然后发现大家都用邻接表

我怎么调也不太对

从早上一直到下午,最终放弃了zkw费用流,回归了单路增广

第一问跑一边最大流

第二问在原图的基础上,加上流量为k且有费用的原边

为了限制多出的流量为k,建一个超级源点,流量为最大流+k,费用为0

跑一边最小费用最大流

 

发表评论