Algoogle

Algorithm for Programming Contest

Ford-Fulkerson法

基本情報


計算量
用途 最大流を求める

F := 最大流の流量 E := 辺の数

解説


始点から終点までにフローを流せるパスが存在する限りそこに流し続ける.
パスに使った辺の容量は減らし, 逆辺の容量を増やす.
非常に単純.
欠点として容量が無理数である場合, 有限回の操作で終了しないことが知られているが, 競技プログラミングにおいてはそのようなケースは稀.

また最大流を利用することで, 2部グラフの最大マッチング問題を解くことができる. ソース->集合A->集合B->シンク と容量1の辺を張ることで最大流が最大マッチングに対応する.

コード


(ford_fulkerson.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
struct edge { int to, cap, rev; };
vector<edge> G[MAX];
bool used[MAX];

void add_edge(int from, int to, int cap) {
    G[from].push_back((edge){to, cap, int(G[to].size())});
    G[to].push_back((edge){from, 0, int(G[from].size()-1)});
}

int dfs(int v, int t, int f) {
    if(v == t) return f;
    used[v] = 1;
    for(int i = 0 ; i < G[v].size(); i++){
        edge &e = G[v][i];
        if(used[e.to] or e.cap <= 0) continue;
        int d = dfs(e.to, t, min(f, e.cap));
        if(d > 0){
            e.cap -= d;
            G[e.to][e.rev].cap += d;
            return d;
        }
    }
    return 0;
}

int ford_fulkerson(int s, int t) {
    int flow = 0, f;
    while(1){
        memset(used, 0, sizeof(used));
        f = dfs(s, t, inf);
        if(f == 0) return flow;
        flow += f;
    }
}

問題


Comments