最小点割集
最编程
2024-07-31 20:38:04
...
在求出最小点割数的基础上，如果再问：具体去掉那些顶点可以使 S-T 不连通。这就是求最小点割集。
这个问题说实话我感觉有点疑惑。
在网上可以找到一个算法就是枚举所有点，将其割掉后再跑最大流，如果最后结果比此前求得的最大流小了，证明这个点就是符合要求的点的其中一个。正确性显然。因为如果这个点符合要求，你提前把他割掉了，结果需要割掉的结点肯定就少了一个。
但是为什么疑惑呢？因为这个算法实在太简单太好理解了。所以总觉得还有更 “优美”，或者说复杂度更低的算法，但又在网上找不到。。。很迷。。。