题解：P4055 [JSOI2009] 游戏

· · 题解

二分图博弈模板题。

题目中给出了一张网格图，众所周知，网格图是一类二分图，所以可以先把它按照纵横坐标之和的奇偶性进行黑白染色，最终得到了一张类似国际象棋棋盘的网格。

我们假设染色规则如下：

若纵横坐标之和为偶数，染黑色；若为奇数，染白色。

将黑色格子视为左部点，白色格子视为右部点，在可到达格子间连边，这就是一张标准的二分图。

然后我们发现「一定存在于这张二分图最大匹配中的点」为必败点，下面我们并不严格地证明这个结论：

由题目样例建立的二分图如上，注意到 1,4,5 三个点为「一定存在于这张二分图最大匹配中的点」，而 6,8 总有一种最大匹配使得它们不存在于匹配中。

如果小 AA 选择 4 作为初始位置，因为 4 一定存在于最大匹配中，所以小 YY 一定有走的位置（即 4 的匹配点），但下一轮的小 AA 因为不能走回去，所以不一定有走的位置，即使是有，更下一轮的小 YY 也可以轻松应对。

综上，最终一定是小 AA 无处可去，故必败。所以上述必败点的补集就是所有必胜点。

那么如何求这个补集（不一定存在于这张二分图最大匹配中的点）呢，我们发现，若 u 点不属于最大匹配，那么 u 连接的所有点的匹配点 v 自然也可以不属于最大匹配（因为 v\to match_v 这条匹配边可以替换为 v\to u）然后在对 match_v 作上述操作。

于是此题的过程就出来了：

  1. 黑白染色，建二分图。
  2. 匈牙利找到最大匹配。
  3. 若最大匹配包含的点数等于所有点数，输出 LOSE，否则输出 WIN。
  4. 遍历所有不在最大匹配中的点作搜索求出「不一定存在于二分图最大匹配中的点」。
  5. 输出这些点。

代码如下：

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e4+10;

const int fx[]={1,0,-1,0};
const int fy[]={0,1,0,-1};

int n,m,match[MAXN],sum;
char c[MAXN];

vector<int> e[MAXN];
bool vis[MAXN],xr[MAXN];// xr 意为 i 是否可以不为最大匹配中的点

bool dfs(int u){
    for(int v:e[u]){
        if(!vis[v]){
            vis[v]=1;
            if(!match[v]||dfs(match[v])){
                match[v]=u;
                match[u]=v; // 一定要带上这句，因为 dfs2 有可能遍历到左部点
                return 1;
            }
        }
    }
    return 0;
}

void dfs2(int u){
    vis[u]=1,xr[u]=1;
    for(int v:e[u]){
        if(!match[v]||vis[match[v]])continue;
        dfs2(match[v]);
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>c[(i-1)*m+j];
    int sum=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(c[(i-1)*m+j]=='#')continue;
            for(int k=0;k<4;k++){
                int tx=i+fx[k],ty=j+fy[k];
                if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&c[(tx-1)*m+ty]=='.')
                    e[(i-1)*m+j].push_back((tx-1)*m+ty);
            }
            if(c[(i-1)*m+j]=='.')sum++; // 统计可达点数目，从而判断是否输出 LOSE
        }
    }
    int sum2=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if((i+j)&1||c[(i-1)*m+j]=='#')continue; // 只对可达黑色点作匈牙利
            memset(vis,0,sizeof vis);
            sum2+=dfs((i-1)*m+j);
        }
    }
    if(sum2<<1==sum&&!(sum&1)){ // 当总可达点数为奇数时，一定有不在最大匹配中的点
        cout<<"LOSE\n";
        return 0;
    }
    cout<<"WIN\n";
    memset(vis,0,sizeof vis);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(!match[(i-1)*m+j]&&(c[(i-1)*m+j]=='.')) // 可达的不在最大匹配中的点
                dfs2((i-1)*m+j);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(xr[(i-1)*m+j])cout<<i<<' '<<j<<'\n';
    return 0;
}