SleepWithMiku @ 2024-12-18 19:42:18
蒟蒻对于一条边的贡献这么理解的：
如果一条边的权值减少了，那么不管在哪条增广路上减少，最终对答案的贡献都是一样的。所以当前这条边无论再哪一条增广路上，能做出的贡献都是一样的。
简而言之，一条边无论在哪条增广路上被消耗，最终对答案的贡献是不变的。
但如果把反向边删去，会在板子题拿到 56pts
有没有大佬解决一下蒟蒻的疑惑，玄关！
by SleepWithMiku @ 2024-12-18 19:43:56
删去反向边的EK
by __JiCanDuck__ @ 2024-12-18 20:00:20
如果一条边的权值减少了，那么不管在哪条增广路上减少，最终对答案的贡献都是一样的。所以当前这条边无论再哪一条增广路上，能做出的贡献都是一样的。
这个明显不成立吧，搜索顺序不同没建反边样例都过不了。
by __JiCanDuck__ @ 2024-12-18 20:02:35
你看样例嘛，因为你把一条边减少，把另一个边增加，按照你的理论，对答案没影响。但实际增加边不一定能流过去。
by __JiCanDuck__ @ 2024-12-18 20:03:49
@SleepWithMiku
by SleepWithMiku @ 2024-12-18 21:26:26
@JiCanDuck 能过样例吧qwq Code
by __JiCanDuck__ @ 2024-12-19 14:36:04
@SleepWithMiku 额，我的问题，我搞个 HACK
by __JiCanDuck__ @ 2024-12-19 14:59:06
9 10 1 6
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
1 7 1
7 8 1
8 9 1
9 6 1
2 9 1 答案是 2，你跑完是 1
因为你找的是最短路，没反边就回不来了
@SleepWithMiku
by SleepWithMiku @ 2024-12-19 16:37:01
@JiCanDuck 谢谢大佬！！！蒟蒻懂了！！！