DINIC的算法，用于多个水槽，单源最大流量问题

Question

我正在尝试实现一种算法，该算法可以找到两个接收器，以便从给定来源的总流量最大。我正在使用dinic的算法，并在上

def maxflow( G,s ):
    g = Graph( G )
    maximum=0
    for i in range( g.V ):
        g.addEdge( ( i, g.V-1, float('inf') ) )
        g2 = copy.deepcopy( g )
        for j in range(g2.V):
            if j == i or j == s or i==s:
                continue
            g2.addEdge( ( j, g.V-1, float('inf') ) )
            maximum = max( g2.DinicMaxflow( s, g.V-1 ), maximum )
            g2 = copy.deepcopy( g )
        g.removeVirtualSink(i)
    return maximum

据我所知，除了检查所有可能的顶点之外，实际上没有更好的方法。我遇到的问题是，由于算法留下残留矩阵，我需要一种方法来存储图形的“默认”状态，以便我可以在每个dinicmaxflow（）调用后返回它，但是deepcopy（）非常慢。 有没有一种方法可以更快地复制数据或优选的数据，以便在每个函数调用后都不必复制数据？

Answer 1

我也遇到了同样的问题，我想到了一个解决方案：在其中您可以额外的节点：将其连接到无限流量范围的所有开始节点，并将其视为启动节点。
在水槽中，同一情况下，连接到一个额外的节点，将其连接到具有INF范围的所有先前的水槽节点，并将此新节点视为最终水槽。
Dinic的算法已经是一种复杂的算法，而多启动和水槽则增加了更复杂的功能。因此，这个技巧可能会有所帮助。我测试了实现，并一直工作。
祝你今天过得愉快。