假如相邻的两列，任意一个割掉的边在相邻列上全部可能的合法边都没有割掉，那么从源点依然可以通过这些合法边到达这个被割掉的边的端点，这条边被割就相当于没被割，所以不会有非法情况出现在最小割里
by zero4338 @ 2021-05-06 17:42:21
这个问题我们机房之前讨论过，有一种确保可以规避这个问题的方法，详见“开门大吉”一题
by _LiM @ 2021-05-06 18:17:29
沿着链建反向无穷边即可在任何情况下避免这个问题（luogu开门大吉），但若限制边连边方向均反向则也没问题，具体反证如下：
@[ix35](/user/113546)
by dengyaotriangle @ 2021-05-06 18:37:34
（至于可不可能下面一列也是割了多个的，有可能，但是如果成环就不可能与 S 连通，所以就肯定成不了环，一定可以找到一个符合条件的）
~~当然我并不保证我证的没问题~~
by dengyaotriangle @ 2021-05-06 18:52:08
说明一下那个图，割多个那两条边取最靠前的两条，而横着的边取最靠前的与 S 连通和最靠后的与 T 连通。
by dengyaotriangle @ 2021-05-06 18:55:40
@[dengyaotriangle](/user/62598)
我明白了，谢谢
by ix35 @ 2021-05-06 19:32:28
@[dengyaotriangle](/user/62598) 大佬第三步我没看太懂，为啥一定存在红色边啊，还有您说的成环是什么啊
by 精神小火 @ 2021-05-06 20:46:09
@[精神小火](/user/152497) 哦，关于环，你可以理解为找到一个这样的，然后沿着“第一个与S连通的位置向前走”，因为一定可以走到S，所以最后一个位置，一定满足前面的所有边都与S连通，这就可以引出矛盾了。
by dengyaotriangle @ 2021-05-06 20:49:05
只要有一个链的某两条割边之间，满足第一个可以从 S 走过来的位置对应的来源的那一条链上直接与 S 连通，就可以导出矛盾，而因为与 S 连通，则沿着任意一个不满足条件的一直向前走，必然存在一个位置直接与 S 连通。
by dengyaotriangle @ 2021-05-06 20:52:29
@[ix35](/user/113546) 为啥不能让边权整体加一个不到inf级别的数字最后再减掉啊
by s_r_f @ 2021-05-06 22:41:57