无向图中基于乘积而非求和的最小权值割问题

这问题挺有意思的——把经典最小割的求和目标换成概率乘积，确实得重新捋捋现有算法能不能套用。我帮你拆解一下核心思路和适用场景：

先搞懂：乘积目标怎么转成求和？ #

核心的数学基础是对数函数的单调性和可加性：对于0到1之间的概率值（正实数），乘积的最小/最大值，完全等价于其对数和的最小/最大值——因为ln(x)在x>0时是严格单调递增的，不会改变最优解的结构。

但要注意：概率p∈(0,1]时，ln(p)是负数，这会直接影响我们对目标的转化方向，得结合具体业务场景来看。

场景1：你想最大化「割有效分离源汇」的概率 #

如果你的概率是指“这条边能被成功切断的概率”，而业务目标是找到一个割，让「所有割边都被切断（从而成功分离源汇）」的概率最大——那这个场景完全适配经典最大流/最小割算法！

具体操作很简单：把每条边的权值替换为 w_e = -ln(p_e)（因为ln(p_e)是负数，所以w_e是正的）。此时，最大化割边的概率乘积 ∏p_e，就等价于最小化变换后的权值和 ∑w_e——这不就是经典最小割的核心目标吗？

所有最大流/最小割的性质（比如强对偶性、增广路定理）都能直接套用，Dinic、Edmonds-Karp这类经典算法也能直接跑，计算出的最小割对应到原问题就是最优解。

场景2：你想最小化割边的概率乘积 #

如果你的业务目标是找到分离源汇的割，让割边的概率乘积最小——那情况就完全不同了。

同样用对数变换：最小化 ∏p_e 等价于最小化 ∑ln(p_e)，而因为ln(p_e)是负数，这又等价于最大化 ∑(-ln(p_e))——也就是找最大割。但最大割在一般图上是NP难问题，经典的最大流/最小割算法根本无法直接解决，相关的性质也不再适用。

除非你的图有特殊结构（比如二分图、平面图），否则不存在多项式时间的精确解法，只能依赖近似算法或启发式思路。

快速验证自己的场景 #

给你个简单的测试例子：假设源点连两条边A（概率0.1）和B（概率0.2），A和B都连到汇点。

• 如果是场景1（最大化割有效概率）：最优割是选B，概率0.2（比选A的0.1、选A+B的0.02都大），对应变换后的权值w_A≈2.302，w_B≈1.609，经典最小割会选权和更小的B，完全正确。
• 如果是场景2（最小化割边乘积）：最优割是选A+B，乘积0.02，这是权和最大的割，经典最小割算法找不到这个解。

所以先明确你的业务目标到底是哪种，再对应找解法就清晰了。

内容的提问来源于stack exchange，提问作者Timo Meijer