UVALive 6525 Attacking Rooks - 二分圖最大匹配經典建模

線段編號算法（DP 預處理）

// 行線段編號
for (int i = 0; i < n; i++) {
    int id = 0;
    for (int j = 0; j < n; j++) {
        if (board[i][j] == 'X') id = 0;
        else if (id == 0) id = ++rowSegCnt;
        rowId[i][j] = id;
    }
}

// 列線段編號
for (int j = 0; j < n; j++) {
    int id = 0;
    for (int i = 0; i < n; i++) {
        if (board[i][j] == 'X') id = 0;
        else if (id == 0) id = ++colSegCnt;
        colId[i][j] = id;
    }
}

匈牙利算法 / HK 算法求最大匹配

vector G[MAXN];
int match[MAXN];
bool vis[MAXN];

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

int maxMatching() {
    int ans = 0;
    memset(match, 0, sizeof(match));
    for (int u = 1; u <= rowSegCnt; u++) {
        memset(vis, 0, sizeof(vis));
        if (dfs(u)) ans++;
    }
    return ans;
}

完整解題框架

1. 讀入棋盤
2. 掃描賦予每個 '.' 其行線段 ID 和列線段 ID
3. 建圖：G[rowId[i][j]].push_back(colId[i][j])
4. 跑最大匹配，輸出匹配數

複雜度分析

• 預處理：O(n²)
• 建圖：O(n²) 邊數 ≤ 空格數
• 匈牙利算法：O(V × E)，實際極快；HK 算法 O(√V × E) 更優
• 總體輕鬆通過 n ≤ 100 甚至更大規模

經典變體延伸

此模型適用於所有「網格放置不相互攻擊棋子且有障礙物」的問題，如放國王、放主教（需按對角線分段）等。