java网络流：添加新的边缘
在最近的一次竞赛中，我被要求设计一个算法，即我们必须设计这样一个算法来找到这样的边
算法应该比O(|E|* h(|V||E|))更快，其中h(|V||E|)是计算最大流量所花费的时间
提前谢谢。如果不清楚，请告诉我
你可以在下面搜索框中键入要查询的问题!
在最近的一次竞赛中，我被要求设计一个算法，即我们必须设计这样一个算法来找到这样的边
算法应该比O(|E|* h(|V||E|))更快，其中h(|V||E|)是计算最大流量所花费的时间
提前谢谢。如果不清楚，请告诉我
# 1 楼答案
另一个解决方案可能是：
第一步。找到包含最小顶点数的最小切割（称其顶点为Vmin）
第二步。找到包含最大顶点数的最小切割（称其顶点为Vmax）
第三步。查找所有链接Vmin和V\Vmax但不属于E的边
为什么会这样？（一） 如果新的uv边包含在每个最小切割中（准确地说：如果它链接最小切割的不同组件），并且（II）最小切割的“组”与并集和交集很接近，则添加新的uv边是好的
复杂性：
对于步骤1,2，我发现了以下很好的算法：How can I find the minimum cut on a graph using a maximum flow algorithm?。这可以用于寻找具有最小和最大顶点的最小割。这似乎是在h（|E | | V |）+O（|V |^3）中运行的，当你检查BFS是否结束时，O（| V | ^3）来自BFS（即不再存在新的剩余相邻）
对于第三步，当我们有O（|Vmin |*|V\Vmax |）时，这就是O（|V | ^2）
因此，步骤1,2,3=h（|E | | V |）+O（|V |^3）
请注意，这只是一个简单的草图：）
# 2 楼答案
（更正了菲利普所说的话。）计算最大流量。提取一个无容量限制的有向图，该图由具有正剩余容量的弧组成。当且仅当存在从源到尾、从头到汇的路径时，添加特定弧会增加最大流量，即弧的引入会创建一条增强路径
在您的示例
{s->a, a->b, a->c, a->d, b->t, c->t, d->t}中，最大流为s-3>a, a-1>b, a-1>c, a-1>d, b-1>t, c-1>t, d-1>t，剩余图具有每个向后弧{a->s, b->a, c->a, d->a, t->b, t->c, t->d}。从s可以到达的顶点是{s}，从t可以到达的顶点是{t}，因此唯一可以增加最大流量的单弧是s->t# 3 楼答案
根据最大流最小割定理[1]，网络中的最大流等于最小割中所有边权的总和。因此，解决方案可能如下所示：
X的最小切割。根据[1]，这是在O(h|V||E|)(S, S')的不同分区的节点，即添加一条边(u,v)，其中u位于S中v位于S'X