POJ 2239 另解：BKDR Hash + 二分匹配

題目理解修正

初見以為樣例中重複的 (1,1) 只能選一次，實際上**每門課可在多個時段上課**，學生可任選其一，不同時段視為不同節點。樣例 5 門課，時段 (1,1) 出現 3 次，分別屬於不同課程，故可同時選取。

BKDR Hash 將二維時段映射為一維節點

時段 (p, q)：p ∈ [1,7]（星期），q ∈ [1,12]（節次）。
用 hash = p * 131 + q 映射為唯一整數（131 為經典 BKDR 基數）。
因範圍極小（≤ 7×131+12=929），**無碰撞風險**，省去雜湊表處理衝突。

建圖與匹配

• 左集合：課程 1..n。
• 右集合：雜湊後的時段節點。
• 邊：課程 i 連接其所有可用時段雜湊值。
• 標準 DFS 匈牙利算法求最大匹配。

完整代碼

#include 
using namespace std;
const int MAXN = 10010;
vector G[MAXN];
int match[MAXN], vis[MAXN], vis_token;

bool dfs(int u) {
    for (int v : G[u]) {
        if (vis[v] == vis_token) continue;
        vis[v] = vis_token;
        if (!match[v] || dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n) {
        for (int i = 1; i <= n; ++i) G[i].clear();
        memset(match, 0, sizeof(match));
        for (int i = 1; i <= n; ++i) {
            int t; cin >> t;
            while (t--) {
                int p, q; cin >> p >> q;
                int key = p * 131 + q; // BKDR Hash
                G[i].push_back(key);
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            ++vis_token;
            if (dfs(i)) ++ans;
        }
        cout << ans << '\n';
    }
    return 0;
}

技術要點總結

1. 雜湊映射：將二維離散座標壓縮為一維整數，簡化圖建模。
2. BKDR Hash 選擇：hash = a * 131 + b，對小範圍整數對完美雜湊。
3. 訪問標記優化：用 vis_token 避免每次 memset，加速 DFS。
4. 複雜度：O(n · E)，n ≤ 300，E ≤ 25200，極快。