夜间模式暗黑模式
字体
阴影
滤镜
圆角
主题色
[ZJOI2010]网络扩容

题面

给定一张有向图,每条边都有一个容量 $C$ 和一个扩容费用 $W$。这里扩容费用是指将容量扩大 $1$ 所需的费用。

求: 1、 在不扩容的情况下,$1$ 到 $N$ 的最大流; 2、 将 $1$ 到 $N$ 的最大流增加 $K$ 所需的最小扩容费用。

题目链接

思路

第一问是一个裸的最大流。

对于第二问,考虑在每条边旁边加一条边,对于边 $(a,b)$,将原来的边费用设为 $0$,再加一条从 $a$ 到 $b$ 的边,费用为  $w$,流量无限。

这样流量流过额外的边时相当于扩容。

题目要求输出最大流在原先的基础上增加 $k$ 的扩容费用,所以我们要限制总流量:在 $n$ 后面额外开一个汇点 $n+1$,连接 $n$ 和 $n+1$,流量为第一问的答案 $ans$ 加上 $k$。从 $1$ 到 $n+1$ 的最小费用最大流的费用就是第二问的答案。

代码

暂无评论

发送评论 编辑评论


				
上一篇
下一篇