最大流模板(Maximum Flow)

秒速五厘米 2022-05-23 05:28 188阅读 0赞

# 最大流模板(Maximum Flow) #

一篇写得通俗易懂介绍最大流的文章:[最大流模板【EdmondsKarp算法，简称EK算法，O(m^2n)】 ][EdmondsKarp_EK_O_m_2n_]

## 残留网络 ##

**残存容量** c~f~(u, v) = c(u, v) - f(u, v);

算法导论中对**残存网络**的一些解释

> 一条边所能允许的反向流量最多将其正向流量抵消. 残存网络中的这些反向边允许算法将发送出来的流量发送回去. 而将流量从同一条边发送回去等同*缩减*该边流量.

## Ford-Fulkerson方法 ##

**增广路径**是残存网络中一条`s`到`t`的路径

**残存容量**是增广路径上能为每条边增加的流量的最大值

不断地沿着增广路径增加路径上的流量, 直到残存网络中不再有任何增广路时就找到了最大流.

## 代码模板 ##

int map[SIZE][SIZE];
    
    int pre[SIZE]; //记录前一个访问的节点
    
    bool visited[SIZE];
    
    int a[SIZE]; //可改进量
    
    bool bfs(int s, int t, int n)
    {
        memset(a, 0, sizeof(a));
        memset(visited, false, sizeof(visited));
        queue<int> q;
        q.push(s);
        a[s] = INF;
        visited[s] = true;
        while (!q.empty())
        {
            int x = q.front();
            q.pop();
            for (int i = 0; i <= n; ++i) //todo
                if (!visited[i] && map[x][i])
                {
                    visited[i] = true;
                    pre[i] = x;
                    q.push(i);
                    a[i] = min(a[x], map[x][i]);
                }
            if (visited[t])
                return true;
        }
        return false;
    }
    
    int maxFlow(int s, int t, int n)
    {
        int flow = 0;
        while (bfs(s, t, n))
        {
            flow += a[t];
            for (int i = t; i != s; i = pre[i])
            {
                map[pre[i]][i] -= a[t];
                map[i][pre[i]] += a[t];
            }
        }
        return flow;
    }

[EdmondsKarp_EK_O_m_2n_]: http://blog.sina.com.cn/s/blog_6cf509db0100uy5n.html