网络流整理

Naive Algorithm

算法步骤

1. 建立residual graph
2. 随机找一条s-t的路径
3. 找到这条路径的bottle neck(瓶颈）
4. 这条路径的所有边-=x
5. flow +=x

flow = 0

while 能找到一条 s -> t 的路径 P:
    x = P 上最小的剩余容量

    for P 上每条边 (u, v):
        residual[u][v] -= x

    flow += x

return flow

由于这个算法是是随机找路径的所以 Naive Algorithm不能保证正确性

Ford-Fulkerson Algorithm

1. Build a residual graph
2. 随机找一条s-t的路径
3. 找到这条路径的 x = bottle neck(瓶颈）
4. 对这条s-t路径上的每一条边c(u,v)-=x 并且flow += x
5. 对这条s-t路径上的每一条边建立反边c(v,u)+=x
6. 直到找不到s-t的路径

初始化残量网络

while (存在 s -> t 的路径)
{
    1. 找到这条路径

    2. 求路径上最小残量
       x = min(...)

    3. 对路径每条边：
       正向容量 -= x
       反向容量 += x

    ans += x
}

F-F算法可以保证这里的最大流的正确性，但是值得诟病的是算法复杂度和结果flow有关，复杂度为我O(fm)如果f= 1e18则无法执行

Edmonds-Karp Algrithom

1. Build a residual graph
2. 使用BFS找一条s-t的最短路径（这里的最短是指边数最小）
3. 找到这条路径的 x = bottle neck(瓶颈）
4. 对这条s-t路径上的每一条边c(u,v)-=x 并且flow += x
5. 对这条s-t路径上的每一条边建立反边c(v,u)+=x
6. 直到找不到s-t的路径

EdmondsKarp(s, t):

    maxFlow = 0

    while BFS(s, t):

        x = INF

        // 从 t 沿 pre 数组回溯到 s
        v = t
        while v != s:
            u = pre[v]
            x = min(x, residual[u][v])
            v = u

        // 更新残量网络
        v = t
        while v != s:
            u = pre[v]

            residual[u][v] -= x
            residual[v][u] += x

            v = u

        maxFlow += x

    return maxFlow

时间复杂度 一次BFS O(E), EK算法可以被证明增广次数最多为VE次 ，所以时间复杂度最坏为O(VE^2)

Dinic Algrithom

1. 建立residual graph
2. 使用BFS建立分层图 （level[u]表示从s到u的最短路径）
3. DFS在分层图中增广推blocking flow（这里只有level[v] = level[u] + 1的边允许增广) 推送blocking flow的时候记得维护残量网络
4. 重新BFS建立level graph

Dinic(s, t):

    maxFlow = 0

    while BFS():

        while true:

            flow = DFS(s, INF)

            if flow == 0:
                break

            maxFlow += flow

    return maxFlow

这里和EK算法的区别就是BFS建立了level graph也就是说他每次推送的一批最短路径的flow然后这一批路径只要block了就推完了