POJ 1273 Drainage Ditches：最大流 Dinic 模板題

題目

有向圖，源點 1（池塘），匯點 M（溪流）。N 條溝渠，每條有容量上限 C。求最大流量。
N ≤ 200，M ≤ 200，C ≤ 10⁷。多測試用例。

解法：Dinic 算法

1. 鄰接表存儲邊（正向容量、反向容量 0）。
2. BFS 分層構建 level 圖。
3. DFS 遞歸尋找阻塞流，cur 當前弧優化。
4. 重複直到無增廣路。

核心代碼

#include 
using namespace std;
const int MAXN = 205, INF = 1e9;

struct Edge { int to, rev, cap; };
vector g[MAXN];
int level[MAXN], cur[MAXN];

void addEdge(int u, int v, int c) {
    g[u].push_back({v, (int)g[v].size(), c});
    g[v].push_back({u, (int)g[u].size()-1, 0});
}

bool bfs(int s, int t) {
    fill(level, level+MAXN, -1);
    queue q; q.push(s); level[s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto &e : g[u]) if (e.cap > 0 && level[e.to] == -1) {
            level[e.to] = level[u] + 1;
            q.push(e.to);
        }
    }
    return level[t] != -1;
}

int dfs(int u, int t, int f) {
    if (u == t) return f;
    for (int &i = cur[u]; i < g[u].size(); ++i) {
        Edge &e = g[u][i];
        if (e.cap > 0 && level[e.to] == level[u] + 1) {
            int ret = dfs(e.to, t, min(f, e.cap));
            if (ret) {
                e.cap -= ret;
                g[e.to][e.rev].cap += ret;
                return ret;
            }
        }
    }
    return 0;
}

int dinic(int s, int t) {
    int flow = 0, inf = 1e9;
    while (bfs(s, t)) {
        fill(cur, cur+MAXN, 0);
        while (int f = dfs(s, t, inf)) flow += f;
    }
    return flow;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    while (cin >> N >> M) {
        for (int i = 0; i < MAXN; ++i) g[i].clear();
        for (int i = 0; i < N; ++i) {
            int u, v, c; cin >> u >> v >> c;
            addEdge(u, v, c);
        }
        cout << dinic(1, M) << "\n";
    }
    return 0;
}

複雜度

• Dinic：O(E √V) 雙層網絡，實測極快。
• 數據範圍小，鄰接表 + 向量足夠。

小結

標準最大流模板題，Dinic 實現簡潔高效，注意多測試用例清空圖、反向邊索引管理。