oiwiki上求最小删除边数的做法的正确性到底怎么证啊
查看原帖
oiwiki上求最小删除边数的做法的正确性到底怎么证啊
856517
mikisayaka楼主2023/8/23 14:07

对于这题第二问,就是求最小删除边数,oiwiki上给的做法是:先正常跑一遍最大流,然后把满流的边容量都改成1,未满流的边容量都改成无穷,然后再跑一次最大流,这时的最大流就是最小删除边数了。

我按这个思路写确实过了,但这个思路真的对吗,会不会是数据太弱了?如果真的是对的,如何证明?

2023/8/23 14:07
加载中...