Edmonds-Karp algorithm

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX_V 55

using namespace std;

struct Edge {
    int to, c, f;
    Edge *r;
    Edge(): Edge(-1, 0) {}
    Edge(int _to, int _c) : to(_to), c(_c), f(0), r(NULL) {}
    int spare() {
        return c - f;
    }
    void addFlow(int _f) {
        f += _f;
        r->f -= _f;
    }
};

int ctoi(char c) {
    if (c >= 'a') return c - 'a';
    else return c - 'A' + 26;
}

int main()
{
    int n, total = 0;
    vector<Edge*> adj[MAX_V];

    scanf("%d", &n);
    while (n--) {
        char u, v;
        int w, uu, vv;
        scanf(" %c %c %d", &u, &v, &w);
        uu = ctoi(u);
        vv = ctoi(v);
        Edge *e1 = new Edge(vv, w), *e2 = new Edge(uu, w);
        e1->r = e2;
        e2->r = e1;
        adj[uu].push_back(e1);
        adj[vv].push_back(e2);
    }

    while (1) {
        int prev[MAX_V], S = ctoi('A'), E = ctoi('Z');
        Edge *path[MAX_V] = { 0 };
        fill(prev, prev + MAX_V, -1);
        queue<int> q;

        q.push(S);
        while (!q.empty() && prev[E] == -1) {
            int v = q.front();
            q.pop();

            for (Edge *e : adj[v]) {
                int next = e->to;
                if (e->spare() > 0 && prev[next] == -1) {
                    q.push(next);
                    prev[next] = v;
                    path[next] = e;
                    if (next == E)
                        break;
                }
            }
        }

        if (prev[E] == -1)
            break;

        int flow = 1e9;
        for (int i = E; i != S; i = prev[i])
            flow = min(flow, path[i]->spare());
        for (int i = E; i != S; i = prev[i])
            path[i]->addFlow(flow);

        total += flow;
    }

    printf("%d", total);

    return 0;
}

https://www.acmicpc.net/problem/6086 에 대한 풀이

코드 템플릿 (C++11)

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX_V 2100

using namespace std;

struct Edge {
    int to, c, f;
    Edge *r;
    Edge() : Edge(-1, 0) {}
    Edge(int _to, int _c) : to(_to), c(_c), f(0), r(NULL) {}
    void addFlow(int _f) {
        f += _f;
        r->f -= _f;
    }
    int spare() {
        return c - f;
    }
};

vector<Edge*> adj[MAX_V];

void insertEdge(int u, int v, int w) {
    Edge *e1 = new Edge(v, w), *e2 = new Edge(u, 0);
    e1->r = e2;
    e2->r = e1;
    adj[u].push_back(e1);
    adj[v].push_back(e2);
}

int main()
{
    // ...

    int S = 0, E = 2, result = 0;
    while (1) {
        queue<int> q;
        int prev[MAX_V];
        Edge *path[MAX_V] = { 0 };

        fill(prev, prev + MAX_V, -1);

        q.push(S);
        while (!q.empty() && prev[E] == -1) {
            int v = q.front();
            q.pop();

            for (Edge *e : adj[v]) {
                int next = e->to;
                if (e->spare() > 0 && prev[next] == -1) {
                    q.push(next);
                    prev[next] = v;
                    path[next] = e;
                    if (next == E)
                        break;
                }
            }
        }

        if (prev[E] == -1)
            break;

        int flow = 1e9;
        for (i = E; i != S; i = prev[i])
            flow = min(flow, path[i]->spare());
        for (i = E; i != S; i = prev[i])
            path[i]->addFlow(flow);

        result += flow;
    }

    // ...
}

정리

• Ford Fulkerson 의 BFS 버전, 시간복잡도는 O(VE^2) 이다.

관련문제

• Total Flow: https://www.acmicpc.net/problem/6086
• 축사 배정: https://www.acmicpc.net/problem/2188
• Crucial Links: https://www.acmicpc.net/problem/5651 ★
• 돼지 잡기: https://www.acmicpc.net/problem/1658
• Avoiding the Apocalypse: https://www.acmicpc.net/problem/10319 ★
• Chess competition: https://www.acmicpc.net/problem/5424
• 도시 왕복하기: https://www.acmicpc.net/problem/2316 ★
• 교실로 가는 길: https://www.acmicpc.net/problem/7616 ★
• 격자 0 만들기 https://www.acmicpc.net/problem/11495 ★
• 숫자판 만들기: https://www.acmicpc.net/problem/2365
• https://www.acmicpc.net/workbook/view/911

참고자료