HDU 3549 過山車：最大流入門模板題（Dinic 算法）

題目大意

K 對可能的男女搭配，M 個女生，N 個男生。每排過山車坐 2 人，必須一男一女。求最多能安排多少對搭乘。本質是二分圖最大匹配，轉化為最大流求解。

建圖模型

• 源點 S → 所有女生（容量 1）
• 女生 → 愿意搭配的男生（容量 1）
• 男生 → 匯點 T（容量 1）
• 最大流值即最大匹配數

Dinic 算法核心步驟

1. BFS 分層：從 S 建立層次圖，`level[v]` 表示到 S 的最短邊數
2. DFS 增廣：只沿 `level[u]+1 == level[v]` 的邊尋找增廣路，用 `iter[]` 當前弧優化
3. 重複直到 BFS 無法到達 T

完整代碼實現

#include <bits/stdc++.h>
using namespace std;

struct Dinic {
    struct Edge { int to, cap, rev; };
    vector> G;
    vector level, iter;
    int N;
    
    Dinic(int n) : N(n), G(n), level(n), iter(n) {}
    
    void addEdge(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});
    }
    
    void bfs(int s) {
        fill(level.begin(), level.end(), -1);
        queue q; level[s] = 0; q.push(s);
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (auto &e : G[v]) if (e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[v] + 1;
                q.push(e.to);
            }
        }
    }
    
    int dfs(int v, int t, int f) {
        if (v == t) return f;
        for (int &i = iter[v]; i < (int)G[v].size(); i++) {
            Edge &e = G[v][i];
            if (e.cap > 0 && level[v] < level[e.to]) {
                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 maxFlow(int s, int t) {
        int flow = 0, INF = 1e9;
        while (true) {
            bfs(s);
            if (level[t] < 0) return flow;
            fill(iter.begin(), iter.end(), 0);
            int f;
            while ((f = dfs(s, t, INF)) > 0) flow += f;
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int K, M, N;
    while (cin >> K >> M >> N) {
        if (K == 0 && M == 0 && N == 0) break;
        Dinic dinic(M + N + 2);
        int S = 0, T = M + N + 1;
        
        for (int i = 1; i <= M; i++) dinic.addEdge(S, i, 1);
        for (int i = 1; i <= N; i++) dinic.addEdge(M + i, T, 1);
        
        for (int i = 0; i < K; i++) {
            int girl, boy; cin >> girl >> boy;
            dinic.addEdge(girl, M + boy, 1);
        }
        
        cout << dinic.maxFlow(S, T) << '\n';
    }
    return 0;
}

關鍵點總結

1. 二分圖匹配 = 最大流：經典轉化模板
2. Dinic 複雜度：O(E√V) 對於二分圖，實際極快
3. 當前弧優化：`iter[]` 避免重複探索已滿邊
4. 分層圖：BFS 保證每次增廣路最短，避免退化

此題是最大流/Dinic 算法的標準入門題，掌握「建圖模板 + BFS分層 + DFS當前弧」三步曲，可解決絕大多數網絡流問題。