最大流算法

﹏ヽ暗。殇╰゛Y 2023-08-17 17:29 138阅读 0赞

最大流问题综述：源节点s ，目的地t，从源节点s和t  之间 ，可以流动的最大量是多少。

s和t之间的每一条边f(u,v)/c(u,v)  表示分开流 和容量

残存网络： 给定流网络G和流量f ，残存网络Gf 由那些仍有空间对流量进行调整的边构成。一条边所能许可的反向流量最多将其正向流量抵消，

3；代码：

NODE_SIZE = 10
    capacity = [ [ 0 for i in range( NODE_SIZE ) ] for j in range( NODE_SIZE ) ]
    parent = [ -1 for i in range( NODE_SIZE ) ]
    visited = [ False for i in range( NODE_SIZE ) ]
    
    def edmonds_karp( start, end ):
        Q = []
        global visited
        visited = [ False for i in range
                    ( NODE_SIZE ) ]
    
        visited[start] = True
        Q.append( start )
    
        while len( Q ) != 0:
            temp = Q.pop( 0 )
            for i in range( NODE_SIZE ):
                if capacity[temp][i] and not visited[i]:
                    print("temp:",temp,"i:",i)
                    visited[i] = True
                    parent[i] = temp
                    Q.append( i )
                    if i == end:
    
                        print()
                        return True
        return False
    
    def ford_fulkerson( start, end ):
        max_flow = 0
        while True:
            if not edmonds_karp( start, end ):
                print("break")
                break
            
            flow = float( "inf" )
            path_node = end
            
            while path_node != start:
                flow = min( flow, capacity[parent[path_node]][path_node] )
                path_node = parent[path_node]
                print("flow:",flow,"parent[path_node]:",parent[path_node],"path_node :",path_node)
               
            path_node = end
            while path_node != start:
                capacity[path_node][parent[path_node]] += flow
                capacity[parent[path_node]][path_node] -= flow
                print("path_node:",path_node,"parent[path_node]:",parent[path_node])
                path_node = parent[path_node]
                
            max_flow += flow
        return max_flow
    
    nodes, edges = map( lambda x: int( x ), input( "Enter number of nodes and edges: " ).split( " " ) )
    
    for e in range( edges ):
        u, v, cap = map( lambda x: int( x ), input( "Enter u, v and capacity: " ).split( " " ) )
        capacity[u][v] = cap
        
    start, end = map( lambda x: int( x ), input( "Enter start_node and end_node: " ).split( " " ) )
    max_flow = ford_fulkerson( start, end )
    print( "max flow: ", max_flow )

输入：  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjUyODA4OQ_size_16_color_FFFFFF_t_70][]

1： ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjUyODA4OQ_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjUyODA4OQ_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjUyODA4OQ_size_16_color_FFFFFF_t_70]: /images/20230808/f7b8febdc9714139ad7b9aafbc1f0d46.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjUyODA4OQ_size_16_color_FFFFFF_t_70 1]: /images/20230808/abfb9ad1a17041928c56938a0f94e814.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjUyODA4OQ_size_16_color_FFFFFF_t_70 2]: /images/20230808/50d4e5a4111f4c0c9a5f142b23b9e4ba.png