網絡流入門：最大流問題解析與 Ford-Fulkerson 算法實現

題目背景

本文探討經典的最大流問題，對應 NYOJ 323、HDU 1532 及 POJ 1273 (Drainage Ditches)。給定一個有向圖，每條邊擁有容量，要求從源點 (1) 到匯點 (m) 的最大流量。

核心思路

這是最基礎的網絡流模型，直接套用 Ford-Fulkerson 方法：不斷尋找增廣路徑，沿路徑增加流量，直到不存在增廣路為止。由於數據規模較小，既可用鄰接矩陣配合 BFS (Edmonds-Karp)，也可用鄰接表實現 DFS 版本的 Ford-Fulkerson。

算法實現要點

1. 鄰接表 + DFS (Ford-Fulkerson)

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 1100;
const int INF = 0x3f3f3f3f;

struct Edge { int to, cap, rev; };
vector<Edge> G[MAXN];
bool used[MAXN];

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

int dfs(int v, int t, int f) {
    if (v == t) return f;
    used[v] = true;
    for (auto &e : G[v]) {
        if (!used[e.to] && e.cap > 0) {
            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 max_flow(int s, int t) {
    int flow = 0;
    while (true) {
        memset(used, 0, sizeof(used));
        int f = dfs(s, t, INF);
        if (f == 0) return flow;
        flow += f;
    }
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        for (int i = 0; i <= m; ++i) G[i].clear();
        for (int i = 0; i < n; ++i) {
            int u, v, c;
            scanf("%d%d%d", &u, &v, &c);
            add_edge(u, v, c);
        }
        printf("%d\n", max_flow(1, m));
    }
    return 0;
}

2. 鄰接矩陣 + BFS (Edmonds-Karp)

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 305;
const int INF = 0x3f3f3f3f;

int cap[MAXN][MAXN], flow[MAXN][MAXN];
int parent[MAXN], min_cap[MAXN];

int bfs(int s, int t, int n) {
    memset(min_cap, 0, sizeof(min_cap));
    queue<int> q;
    q.push(s);
    min_cap[s] = INF;
    parent[s] = -1;

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v = 1; v <= n; ++v) {
            if (!min_cap[v] && cap[u][v] > flow[u][v]) {
                parent[v] = u;
                min_cap[v] = min(min_cap[u], cap[u][v] - flow[u][v]);
                if (v == t) return min_cap[t];
                q.push(v);
            }
        }
    }
    return 0;
}

int max_flow(int s, int t, int n) {
    memset(flow, 0, sizeof(flow));
    int total = 0, f;
    while ((f = bfs(s, t, n)) > 0) {
        total += f;
        for (int v = t; v != s; v = parent[v]) {
            int u = parent[v];
            flow[u][v] += f;
            flow[v][u] -= f;
        }
    }
    return total;
}

複雜度分析

• DFS 版 Ford-Fulkerson：最壞情況 O(E * max_flow)，但實測於小數據極快。
• BFS 版 Edmonds-Karp：O(V * E^2)，穩健且易於理解。

總結

最大流是網絡流的基石，掌握增廣路思想與兩種常見實現（鄰接表 DFS、鄰接矩陣 BFS）至關重要。後續可進階學習 Dinic、ISAP 等更高效算法。