原因
应该都是写成最小费用最大流
就是如果流没有到最大就继续跑下去
题目要求的是
最小费用可行流
就是跑到终点,还不能亏钱,流不一定要最大
具体可以看一下这篇2023CCPC女生赛 D - 金人旧巷市廛喧
的代码中的一段
第34到第36行
就是最小费用可行流和最小费用最大流的区别
if(dis[t] == inf || dis[t]>=0) return 0; //如果无法到终点,或者到终点不赚钱或亏钱了,那以后就都不继续走了(证明略)
//重点!!!dis[t]>=0就是【最小费用可行流】比起【最小费用最大流】需要加的唯一一句代码!!!
else return 1; //能到终点,还能赚钱,这次走比不走好
————————————————
版权声明:本文为CSDN博主「胡豆豆今天也在学算法」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/qq_66616036/article/details/134052267