如题,为什么这样建完图(第一篇题解的)跑一遍最大流就能过了?
目前我的理解是: 题目求最大收益,实际上是在所有收益中去掉一些收益,使剩下的最大。所以先把所有收益都选了,再割掉最少的,剩下最多,所以跑最小割。
建图时,每种作物必须在A地与B地中舍去一个,这种"或"的条件,就要"串联"。所以对于作物i,左边连S,边权为ai,右边连T,边权为bi。这样,最小割时,就会在两条边中自动选一个割掉(因为不能让图连通),也保证了只割掉一个(因为是最小割),就满足了题目要求。
但是,为什么额外收益是那样连的啊?为什么割掉了1,c1就会自动割掉?
想了一下午了,求助各位dalao,十分感谢!!