Ford Fulkerson (포드 풀커슨)

포드 풀커슨, 포드-풀커슨, ford-fulkerson 알고리즘, O((V+E)*f) 이므로 (f: 용량의 크기 최대), O(VE^2) 인 Edmonds-Karp algorithm을 사용하시오

코드

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

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];
int S, E;
int pre[MAX_V];
Edge *path[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);
}

bool ff(int v) {
    if (v == E)
        return true;

    for (Edge *e : adj[v]) {
        int next = e->to;
        if (e->spare() > 0 && pre[next] == -1) {
            pre[next] = v;
            path[next] = e;
            if (ff(next))
                return true;
        }
    }

    return false;
}

int main()
{
    int t, n, m, a, b, i, j;

    scanf("%d", &t);
    while (t--) {
        int total = 0;
        scanf("%d%d", &n, &m);
        for (i = 0; i < m; i++) {
            scanf("%d%d", &a, &b);
            insertEdge(0, 2 + i, 1);
            for (j = a; j <= b; j++)
                insertEdge(2 + i, 1002 + j, 1);
        }
        for (i = 1; i <= n; i++)
            insertEdge(1002 + i, 1, 1);

        S = 0, E = 1;
        while (1) {
            fill(pre, pre + MAX_V, -1);
            memset(path, 0, sizeof(path));

            ff(S);

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

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

            total += flow;
        }

        printf("%d\n", total);
    }

    return 0;
}

https://www.acmicpc.net/problem/9576를 포드풀커슨으로 풀었으 시간초과 났음.. 이분매칭으로 풀어야할듯

정리

  • 모든 간선의 유량은 0으로 시작한다
  • 소스에서 싱크로 유량을 보낼 수 있다면, 반복하여 보낸다.
    • 증가 경로 (augmenting path) : 유량을 보내는 경로
    • 간선의 용량과 유량의 차이를 잔여 용량(desidual capacity) 라 한다. 잔여 용량을 r(u, v) 라 할 때 다음이 성립하다.
      • r(u, v) = c(u, v) - f(u, v)
      • 하지만 유량의 대칭성을 고려해야 한다.
    • 흘려 보낼 수 있는 유량은 증가 경로에 포함된 간선 중 가장 작은 잔여 용량이다.
    • 유량의 대칭성을 고려한 잔여 용량은 다음과 같다.
      • r(u, v) = c(u, v) - f(u, v) + f(v, u)

참고 자료

  • 종만북 - 993 페이지 ~

관련 문제

results matching ""

    No results matching ""