ppip @ 2022-08-30 17:00:45
原帖描述出现问题不给了。
给定一个网络，点数、边数、每个边的容量同阶，每个边的费用 0 或 1，并且不同于一般的费用流，不管这条边的流量多少，费用都是固定的，求最大流的前提下的最小费用。
所有费用为1的边的入点一定是源点。
要求至少提供正确性证明的思路。
by rzh123 @ 2022-08-30 17:04:53
Cu Ball
by dehsirehC @ 2022-08-30 17:08:03
我会暴搜
by Catium @ 2022-08-30 17:10:10
不管流量是多少费用都固定,某条边上0流量也计费吗?
如果是的话,任意最大流的方案费用都是一样的啊.
by bamboo12345 @ 2022-08-30 17:11:39
@Catium 只是有一些边是这样有一些还是正常算
by Catium @ 2022-08-30 17:13:48
@bamboo123 题主说
不管这条边的流量多少，费用都是固定的
那这样的话我理解就是0流量也计费, 也就是无论如何都计费, 那任意最大流, 甚至不流的费用都是一样的啊, 直接把所有费用不为零的的加起来就完了吧.
by bamboo12345 @ 2022-08-30 17:35:28
@Catium 你没有懂楼主的意思，楼主想说的是有一些边零流的时候0费用，否则就是有一个固定的费用，剩余的边就是正常的单位权值
by ppip @ 2022-08-30 20:56:37
@bamboo123 实际上，所有的边都满足
by bamboo12345 @ 2022-08-30 21:11:13
@ppip 好像也是,但是就算是这样也难做啊
by ppip @ 2022-08-30 21:14:57
@bamboo123 我在想，正常的写EK，每条边存一下初始容量，然后spfa现在容量=初始容量且有费用的边长就记作1，否则记作0.
但我不太会证明/证伪这个东西的正确性。
by bamboo12345 @ 2022-08-30 21:34:11
@ppip 或者说你建一个边权为0的容量无限的边再搞一个边权为1容量为1的边,判断的时候强制先走边权为1的边?