POJ 2289 Jamie's Contact Groups：二分答案 + 最大流（Dinic）

問題描述

n 個人，m 個組。每人屬於若干組。每人分配到一個組，每組可容納多人。求最小化「最大組人數」（即每組最多人數的最小可能值）。

建模：二分 + 最大流

• 二分答案 max_group_size (0~n)。
• 流網絡：
    源 S → 每人 (容量 1)。
    每人 → 其屬於的組 (容量 1)。
    每組 → 匯 T (容量 = max_group_size)。
    最大流 = n 則可行。

Dinic 算法

分層圖 + 阻塞流，O(E√V) 對二分圖匹配極快。
邊數：S→人 n，人→組 ≤ n×m，組→T m。總 ≤ 50000+。

代碼實現 (C++)

#include <bits/stdc++.h>
using namespace std;
struct Dinic {
    struct Edge { int to, cap, rev; };
    vector> G;
    vector level, it;
    Dinic(int n) : G(n), level(n), it(n) {}
    void add_edge(int u, int v, int cap) {
        G[u].push_back({v, cap, (int)G[v].size()});
        G[v].push_back({u, 0, (int)G[u].size()-1});
    }
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue q; level[s] = 0; q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto& e : G[u]) if (e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[u] + 1;
                q.push(e.to);
            }
        }
        return level[t] >= 0;
    }
    int dfs(int u, int t, int f) {
        if (u == t) return f;
        for (int& i = it[u]; i < G[u].size(); ++i) {
            Edge& e = G[u][i];
            if (e.cap > 0 && level[u] < 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 max_flow(int s, int t) {
        int flow = 0, inf = 1e9;
        while (bfs(s, t)) {
            fill(it.begin(), it.end(), 0);
            int f;
            while ((f = dfs(s, t, inf)) > 0) flow += f;
        }
        return flow;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m, n || m) {
        vector> groups(n);
        string line; getline(cin, line); // 吃換行
        for (int i = 0; i < n; ++i) {
            getline(cin, line);
            stringstream ss(line);
            int g; while (ss >> g) groups[i].push_back(g);
        }
        int lo = 0, hi = n, ans = n;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            int S = 0, T = n + m + 1;
            Dinic dinic(T + 1);
            for (int i = 0; i < n; ++i) dinic.add_edge(S, 1+i, 1);
            for (int i = 0; i < n; ++i)
                for (int g : groups[i])
                    dinic.add_edge(1+i, 1+n+g, 1);
            for (int g = 0; g < m; ++g)
                dinic.add_edge(1+n+g, T, mid);
            if (dinic.max_flow(S, T) == n) { ans = mid; hi = mid - 1; }
            else lo = mid + 1;
        }
        cout << ans << '\n';
    }
    return 0;
}

複雜度

• 二分：O(log n)。
• 每次 Dinic：O(E√V) ≈ 5e4 × 300 ≈ 1.5e7。
• 總：O(log n × E√V) ≈ 3e7，1 秒內可行。

關鍵點

• 「最小化最大負載」經典二分 + 最大流模型。
• 輸入解析：每行數字不定，用 getline + stringstream。
• Dinic 模板通用性強，適用於所有最大流/二分圖匹配問題。

這題是「負載均衡 + 最大流」的教科書級應用，二分答案將決策問題轉化為可行性判斷，Dinic 高效求解。