最大流的三种算法:Ford-Fulkson、Edmons-Karp、Dinic

最大流的三种算法:Ford-Fulkson、Edmons-Karp、Dinic

这里不介绍算法,只提供模板代码。所有代码基于【P3376】【模板】网络最大流 – 洛谷一题。

Ford-Fulkson

// Code by KSkun, 2017/11
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

struct io {
    char buf[1 << 26], *s;

    io() {
        fread(s = buf, 1, 1 << 26, stdin);
    }

    inline int read() {
        register int res = 0;
        while(*s < '0' || *s > '9') s++;
        while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
        return res;
    }
} ip;

#define read ip.read

const int MAXN = 100005;
const int INF = 1e9;

struct Edge {
    int to, cap, rev;
    Edge(int to, int cap, int rev): to(to), cap(cap), rev(rev) {}
};

std::vector<Edge> vec[MAXN];
bool vis[MAXN];

inline void addedge(int u, int v, int cap) {
    vec[u].push_back(Edge(v, cap, vec[v].size()));
    vec[v].push_back(Edge(u, 0, vec[u].size() - 1));
}

// Ford-Fulkerson DFS
inline int dfs(int u, int t, int f) {
    if(u == t) return f;
    vis[u] = true;
    for(int i = 0; i < vec[u].size(); i++) {
        int v = vec[u][i].to;
        if(!vis[v] && vec[u][i].cap > 0) {
            int nxt = dfs(v, t, std::min(f, vec[u][i].cap));
            if(nxt > 0) {
                vec[u][i].cap -= nxt;
                vec[v][vec[u][i].rev].cap += nxt;
                return nxt;
            }
        } 
    }
    return 0;
}

inline int max_flow(int s, int t) {
    int flow = 0;
    for(;;) {
        memset(vis, 0, sizeof vis);
        int f = dfs(s, t, INF);
        if(f == 0) return flow;
        flow += f;
    }
}

int n, m, s, t, ut, vt, wt;

int main() {
    n = read();
    m = read();
    s = read();
    t = read();
    for(int i = 0; i < m; i++) {
        ut = read();
        vt = read();
        wt = read();
        addedge(ut, vt, wt);
    }
    printf("%d", max_flow(s, t));
    return 0;
}

Edmons-Karp

// Code by KSkun, 2017/11
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility> 
typedef std::pair<int, int> pairi;

struct io {
    char buf[1 << 26], *s;

    io() {
        fread(s = buf, 1, 1 << 26, stdin);
    }

    inline int read() {
        register int res = 0;
        while(*s < '0' || *s > '9') s++;
        while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
        return res;
    }
} ip;

#define read ip.read

const int MAXN = 100005;
const int INF = 1e9;

struct Edge {
    int to, cap, rev;
    Edge(int to, int cap, int rev): to(to), cap(cap), rev(rev) {}
};

std::vector<Edge> vec[MAXN];
std::queue<int> que;
int f[MAXN];
pairi pre[MAXN];

inline void addedge(int u, int v, int cap) {
    vec[u].push_back(Edge(v, cap, vec[v].size()));
    vec[v].push_back(Edge(u, 0, vec[u].size() - 1));
}

// Edmons-Karp BFS

inline int max_flow(int s, int t) {
    int flow = 0;
    for(;;) {
        memset(f, 0, sizeof f);
        while(!que.empty()) que.pop();
        que.push(s);
        f[s] = INF;
        while(!que.empty()) {
            int u = que.front();
            que.pop();
            for(int i = 0; i < vec[u].size(); i++) {
                int v = vec[u][i].to;
                if(f[v] == 0 && vec[u][i].cap > 0) {
                    pre[v] = std::make_pair(u, i);
                    f[v] = std::min(f[u], vec[u][i].cap);
                    que.push(v);
                }
            }
            if(f[t] != 0) break;
        }
        if(f[t] == 0) break;
        for(int u = t; u != s; u = pre[u].first) {
            vec[pre[u].first][pre[u].second].cap -= f[t];
            vec[u][vec[pre[u].first][pre[u].second].rev].cap += f[t];
        }
        flow += f[t];
    }
    return flow;
}

int n, m, s, t, ut, vt, wt;

int main() {
    n = read();
    m = read();
    s = read();
    t = read();
    for(int i = 0; i < m; i++) {
        ut = read();
        vt = read();
        wt = read();
        addedge(ut, vt, wt);
    }
    printf("%d", max_flow(s, t));
    return 0;
}

Dinic

// Code by KSkun, 2017/11
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>

struct io {
    char buf[1 << 26], *s;

    io() {
        fread(s = buf, 1, 1 << 26, stdin);
    }

    inline int read() {
        register int res = 0;
        while(*s < '0' || *s > '9') s++;
        while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
        return res;
    }
} ip;

#define read ip.read

const int MAXN = 100005;
const int INF = 1e9;

struct Edge {
    int to, cap, rev;
    Edge(int to, int cap, int rev): to(to), cap(cap), rev(rev) {}
};

std::vector<Edge> vec[MAXN];
std::queue<int> que;
int level[MAXN];

inline void addedge(int u, int v, int cap) {
    vec[u].push_back(Edge(v, cap, vec[v].size()));
    vec[v].push_back(Edge(u, 0, vec[u].size() - 1));
}

// Dinic 

inline bool bfs(int s, int t) {
    memset(level, -1, sizeof level);
    level[s] = 0;
    que.push(s);
    while(!que.empty()) {
        int u = que.front();
        que.pop();
        for(int i = 0; i < vec[u].size(); i++) {
            int v = vec[u][i].to;
            if(level[v] == -1 && vec[u][i].cap > 0) {
                level[v] = level[u] + 1;
                que.push(v);
            }
        } 
    }
    return level[t] != -1;
}

inline int dfs(int u, int t, int left) {
    if(u == t || left == 0) return left;
    int flow = 0;
    for(int i = 0; i < vec[u].size(); i++) {
        int v = vec[u][i].to;
        if(vec[u][i].cap > 0 && level[v] == level[u] + 1) {
            int d = dfs(v, t, std::min(left, vec[u][i].cap));
            if(d > 0) {
                vec[u][i].cap -= d;
                vec[v][vec[u][i].rev].cap += d;
                flow += d;
                left -= d;
                if(left == 0) break;
            }
        }
    }
    return flow;
}

inline int max_flow(int s, int t) {
    int flow = 0;
    while(bfs(s, t)) {
        flow += dfs(s, t, INF);
    }
    return flow;
}

int n, m, s, t, ut, vt, wt;

int main() {
    n = read();
    m = read();
    s = read();
    t = read();
    for(int i = 0; i < m; i++) {
        ut = read();
        vt = read();
        wt = read();
        addedge(ut, vt, wt);
    }
    printf("%d", max_flow(s, t));
    return 0;
}


发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据