_LanFeng_ @ 2024-09-01 10:32:31
按照算法导论学的，其推导非常严谨，但是要求网络没有反向边（若
by jason_sun @ 2024-09-01 10:45:16
反边不影响正确性
by _LanFeng_ @ 2024-09-01 10:47:23
@jason_sun 那为啥黑书要专门强调无反边呢？我看其证明确实也用了无反边的性质才能继续往下推导
by jason_sun @ 2024-09-01 13:15:52
双向四边
by Stairs_upon_temple @ 2024-09-01 14:15:48
@LanFeng 在有反边的情况下考虑新增一个点，正确性可以保证。
by _LanFeng_ @ 2024-09-01 21:19:28
@Stairs_upon_temple 是的。但是为什么我们代码没有这步操作？就是说题目如果给的图有反向边，我们的代码却没有体现这种加点的操作？
by Stairs_upon_temple @ 2024-09-01 21:26:34
@LanFeng z你可以在代码中加入该操做，但没必要，我这个图只是来解释为什么直接建反边是没问题的。相当于直接建反边可以等价于新建一个点
by _LanFeng_ @ 2024-09-01 21:35:48
@Stairs_upon_temple 我就是这点有疑惑。现在的逻辑是我们现在无反向边的网络上严格证明了FF的正确性，然后现在有反向边的网络我们等价转化为无反向边的网络，然后说明这两者的最大流相等。那么我们不应该是去求后者的最大流，从而得到前者的最大流吗？您说的直接建反边可以等价于新建一个点这一点就相当于去求前者的最大流了，但算法却是基于后者的正确性。如果这种算法是正确的，那么就是说您说的这一点是对的。所以就是说这一点可以证明，是吗？
by Stairs_upon_temple @ 2024-09-01 21:45:37
@LanFeng 在无反向边的网络最大流正确的前提下二图的最大流是可以跑出来的，而在我的表达中一图和二图在实际的计算过程中是等价的。
你可以这么理解，假设你要对一图跑最大流，他等价于二图跑最大流，因为二图的正确性可以保证，所以在我的理解里一图中直接跑最大流是正确的，但如果你质疑为什么图一等价图二，那我无能为力，~~因为我教练也没讲~~
by Stairs_upon_temple @ 2024-09-01 21:48:11
@LanFeng 反正你记住就可以了，网络流的题基本上不会涉及到在网络内部操作，所以这些概念的东西没必要特别去钻，网络流的难点在于图论建模，和模型转化，反正模板记住，多做题，多思考，多积累经验就对了
by _LanFeng_ @ 2024-09-01 22:03:31
@Stairs_upon_temple 我想了一下，您看是不是这么回事。我们对两个图同时跑FF，那么两个图在任意时刻的残存网络都是一一对应的，比如下图
左边的图是题目给我们的图，右边的图是等价转化后的图（其中
所以我们对图二跑FF，某一时刻找到了一条增广路