最大流 FF EK算法

古城微笑少年丶 2022-05-27 03:07 158阅读 0赞

EK是最大流中最简单也是最慢的，要学Dinic。

费用流是spfa+巴拉巴拉，还有最小割。

推荐一个EK算法视频：https://www.bilibili.com/video/av18567992?from=search&seid=16517892414807345163

A Plug for UNIX：https://blog.csdn.net/keshuai19940722/article/details/16884109

田鼠和老鹰题目的最大流版本：http://blog.sina.com.cn/s/blog\_6cad76090100s1q4.html

模板来自：https://blog.csdn.net/txl199106/article/details/64441994

数组实现：

#include <queue>
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    using namespace std;
    const int MAXN = 300;
    const int MAX_INT = ((1 << 31) - 1);
    
    int n;                                      // 图中点的数目
    int pre[MAXN];                              // 从 s - t 中的一个可行流中, 节点 i 的前序节点为 Pre[i];
    bool vis[MAXN];                             // 标记一个点是否被访问过
    int mp[MAXN][MAXN];                         // 记录图信息
    
    bool bfs(int s, int t){
        queue <int> que;
        memset(vis, 0, sizeof(vis));
        memset(pre, -1, sizeof(pre));
        pre[s] = s;
        vis[s] = true;
        que.push(s);
        while(!que.empty()){
            int u = que.front();
            que.pop();
            for(int i = 1; i <= n; i++){
                if(mp[u][i] && !vis[i]){
                    pre[i] = u;
                    vis[i] = true;
                    if(i == t) return true;
                    que.push(i);
                }
            }
        }
        return false;
    }
    
    int EK(int s, int t){
        int ans = 0;
        while(bfs(s, t)){
            int mi = MAX_INT;
            for(int i = t; i != s; i = pre[i]){
                mi = min(mi, mp[pre[i]][i]);
            }
            for(int i = t; i != s; i = pre[i]){
                mp[pre[i]][i] -= mi;
                mp[i][pre[i]] += mi;
            }
            ans += mi;
        }
        return ans;
    }

邻接表实现：

const int MAXN = 430;
    const int MAX_INT = (1 << 30);
    
    struct Edge{
        int v, nxt, w;
    };
    
    struct Node{
        int v, id;
    };
    
    int n, m, ecnt;
    bool vis[MAXN];
    int head[MAXN];
    Node pre[MAXN];
    Edge edge[MAXN];
    
    void init(){
        ecnt = 0;
        memset(edge, 0, sizeof(edge));
        memset(head, -1, sizeof(head));
    }
    
    void addEdge(int u, int v, int w){
        edge[ecnt].v = v;
        edge[ecnt].w = w;
        edge[ecnt].nxt = head[u];
        head[u] = ecnt++;
    }
    
    bool bfs(int s, int t){
        queue <int> que;
        memset(vis, 0, sizeof(vis));
        memset(pre, -1, sizeof(pre));
        pre[s].v = s;
        vis[s] = true;
        que.push(s);
        while(!que.empty()){
            int u = que.front();
            que.pop();
            for(int i = head[u]; i + 1; i = edge[i].nxt){
                int v = edge[i].v;
                if(!vis[v] && edge[i].w){
                    pre[v].v = u;
                    pre[v].id = i;
                    vis[v] = true;
                    if(v == t) return true;
                    que.push(v);
                }
            }
        }
        return false;
    }
    
    int EK(int s, int t){
        int ans = 0;
        while(bfs(s, t)){
            int mi = MAX_INT;
            for(int i = t; i != s; i = pre[i].v){
                mi = min(mi, edge[pre[i].id].w);
            }
            for(int i = t; i != s; i = pre[i].v){
                edge[pre[i].id].w -= mi;
                edge[pre[i].id ^ 1].w += mi;
            }
            ans += mi;
        }
        return ans;
    }
    
    // 加边
    addEdge(u, v, w);
    addEdge(v, u, 0);
    // 调用
    int ans = EK(s, t);