BZOJ 3175 [TJOI2013] 攻擊裝置：二分圖最大獨立集裸題解法（匈牙利算法）

題目給定 N×N 01 矩陣，0 表示可放置攻擊裝置。裝置攻擊範圍為「日」字 8 個位置（類似國際象棋騎士移動）。求互不攻擊條件下最多放置裝置數。N ≤ 200。

建模思路：二分圖最大獨立集

1. 將矩陣每個 0 格視為圖中一個頂點。
2. 若兩格互為騎士移動關係，連一條無向邊 → 構成二分圖（按 (x+y)%2 黑白染色）。
3. 「互不攻擊」即選取頂點集合中無邊相連 → 最大獨立集。
4. 二分圖中：最大獨立集 = 總頂點數 - 最大匹配數（Kőnig 定理）。

算法流程

1. 掃描矩陣，給每個 0 格編號 id = (x-1)*N + y。
2. 對黑格（(x+y)%2==1），向 8 個方向嘗試連邊到白格（0 格）。
3. 跑匈牙利算法（DFS增廣路）求最大匹配。
4. 答案 = 總0格數 - 匹配數。

C++ 代碼（含優化讀入）

#include 
using namespace std;
const int MAXN = 40005;
int n, cnt, ans, head[MAXN], match[MAXN];
int dx[8] = {-1,-2,1,2,-1,-2,1,2};
int dy[8] = {-2,-1,-2,-1,2,1,2,1};
bool f[205][205], vst[MAXN];
char s[205];

struct Edge { int to, next; } e[MAXN * 8];

inline int id(int x, int y) { return (x-1)*n + y; }

inline void addEdge(int u, int v) {
    e[++cnt] = {v, head[u]};
    head[u] = cnt;
}

bool dfs(int u) {
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (vst[v]) continue;
        vst[v] = true;
        if (!match[v] || dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s+1);
        for (int j = 1; j <= n; j++) f[i][j] = (s[j] == '0');
    }
    // 建圖：黑格向白格連邊
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (f[i][j] && (i+j)%2)
                for (int k = 0; k < 8; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x<1 || y<1 || x>n || y>n) continue;
                    if (!f[x][y]) continue;
                    addEdge(id(i,j), id(x,y));
                }
    // 統計總0格數
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (f[i][j]) ans++;
    // 匈牙利求最大匹配
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (f[i][j] && (i+j)%2) {
                memset(vst, 0, sizeof(vst));
                if (dfs(id(i,j))) ans--;
            }
    printf("%d\n", ans);
    return 0;
}

關鍵點總結

• 二分圖染色：(x+y)%2 保證騎士移動總在不同色之間。
• 邊的方向性：只需從黑格向白格連邊，匈牙利算法從左部（黑格）出發增廣。
• 複雜度：O(V*E)，V≤40000，E≤8V，完全滿足時限。
• 樣例驗證：

  輸入: 3 / 010 / 000 / 100
  輸出: 4