BZOJ 1443：JSOI2009 Game——二分圖博弈與最大匹配

題目描述

m×n 棋盤，部分格子有障礙。先手放棋子，雙手輪流移動到相鄰無障礙未訪問格子，無法移動者負。判斷先手必勝策略及所有必勝起始位置。

二分圖博弈模型

棋盤黑白染色（鄰接異色）構成二分圖。遊戲等價於：先手選起點，後手沿匹配邊走，先手再沿匹配邊走... 關鍵定理：

• 若存在最大匹配不覆蓋某頂點，先手選該點必勝
• 若存在完美匹配，先手必敗

求必勝起始點集合

1. 求最大匹配
2. 從所有未匹配左頂點出發，沿「非匹配邊→匹配邊→非匹配邊...」交替 DFS，到達的左頂點均為必勝點
3. 交換左右部重複上述，得到右部必勝點
4. 合併輸出

匈牙利算法 + 交替路 DFS

// 匈牙利求最大匹配
bool hungary(int u) {
    for(int e=head[u]; e; e=E[e].next) {
        int v=E[e].to;
        if(vis[v]) continue;
        vis[v]=1;
        if(!match[v] || hungary(match[v])) {
            match[v]=u; return true;
        }
    }
    return false;
}

// 交替路 DFS 標記必勝點
void dfs_win(int u, bool win[]) {
    win[u]=true;
    for(int e=head[u]; e; e=E[e].next) {
        int v=E[e].to, w=match[v];
        if(w && !win[w]) dfs_win(w, win);
    }
}

複雜度

• 匈牙利：O(V·E) ≈ 10000 × 40000，常數小實際極快
• DFS：O(V+E)