夜间模式
字体
阴影
滤镜
主题色
[SDOI2009]晨跑

题目描述

题目大意:给出一张点数为 $n$,边数为 $m$ 的有向图,除了点 $1$ 和点 $n$ 外每个点和每条边只能走一次,求从点 $1$ 到点 $n$ 的最小费用最大流。

题目链接

思路

这道题主要是题面难理解。

由于一个点只能经过一次,我们一个点拆分为两个点,中间连一条流量为 $1$,费用为 $0$ 的边。

注意点 $1$ 和 点 $n$ 因为可以走不止一次,所以它们拆开的点中间的边的流量要设为无穷。

这样我们就保证了除点 $1$ 和点 $n$ 外每个点只能经过一次,然后跑一遍费用流即可。

代码

暂无评论

发送评论


				
上一篇
下一篇