POJ 2446 Chessboard：二分圖最大匹配判定多米諾鋪滿

問題建模

n×m 棋盤（n,m ≤ 500），部分格子有洞不可用。用 1×2 多米諾骨牌覆蓋所有無洞格子，不重疊。判定是否可完全覆蓋。

二分圖轉化

棋盤著色：(i+j) % 2 == 0 為黑點，1 為白點。多米諾必覆蓋一黑一白 → 點之間建邊。求最大匹配，若匹配數 = 總可用格子數 / 2 則可完全覆蓋。

匈牙利算法實現

vector g[maxn];
int from[maxn];
bool used[maxn];

bool dfs_match(int u) {
    for (int v : g[u]) if (!used[v]) {
        used[v] = true;
        if (from[v] == -1 || dfs_match(from[v])) {
            from[v] = u;
            return true;
        }
    }
    return false;
}

int hungarian(int n) {
    memset(from, -1, sizeof(from));
    int match = 0;
    for (int u = 1; u <= n; u++) {
        memset(used, 0, sizeof(used));
        if (dfs_match(u)) match++;
    }
    return match;
}

圖構建細節

• 編號：id = (r-1)*m + c（1-based）
• 僅從黑點向四鄰域白點連邊（避免重複）
• 跳過有洞格子
• 總可用格子為奇數直接輸出 NO

完整代碼結構

int main() {
    while (~scanf("%d%d%d", &n, &m, &k)) {
        memset(hole, 0, sizeof(hole));
        for (i=0; in||nj<1||nj>m||hole[ni][nj]) continue;
                int v = (ni-1)*m + nj;
                g[u].push_back(v);
            }
        }
        
        int match = hungarian(n*m);
        puts(match == total/2 ? "YES" : "NO");
    }
}

複雜度

• 點數 ≤ 250000，邊數 ≤ 4×點數
• 匈牙利 O(V×E) 實際較快，配合稀疏圖可通過
• 輸入量大，使用 scanf/快速 IO