BZOJ2437:[Noi2011]兔兔与蛋蛋 博弈论+二分图

思路:

本题的模型转换十分巧妙:

仅考虑空格移动,注意到空格移动的路径事实上是黑白相间,且不自交的路径.

这样我们黑白染色变成二分图,转化为二分图上的博弈问题.

显然的性质是从一个点出发先手必胜当且仅当这个点是二分图最大匹配的必须点.

若这个点没有匹配点,先手必败;否则将这个点的匹配点的匹配点设为0,删除这个点,并从这个点的匹配点开始增广.若能够增广,显然这个点不是必须点.

这样只需增广\(O(K)\)次,时间复杂度\(O(KN^4)\).

(另外本沙茶终于明白匈牙利算法是怎回事了...)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
 
#define N 41
int ano[N*N];
bool changed[N*N];
 
int head[N*N],next[N*N<<2],end[N*N<<2];
inline void addedge(int a,int b){
    static int q=1;
    end[q]=b;
    next[q]=head[a];
    head[a]=q++;
}
inline void make(int a,int b){
    addedge(a,b);
    addedge(b,a);
}
 
bool del[N*N];
inline bool dfs(int x){
    if(del[x])return 0;
    for(int j=head[x];j;j=next[j]){
        if(!changed[end[j]]&&!del[end[j]]){
            changed[end[j]]=1;
            if(!ano[end[j]]||dfs(ano[end[j]])){
                ano[x]=end[j],ano[end[j]]=x;
                return 1;
            }
        }
    }
    return 0;
}
 
char s[N];
int map[N][N],lab[N][N];
inline int hash(char c){
    if(c=='X')return 0;
    if(c=='O')return 1;
    return 2;
}
 
inline int getdis(int x,int y){
    return x>y?x-y:y-x;
}
 
#define Q 2010
bool win[Q];
 
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
     
    register int i,j;
    for(i=1;i<=n;++i){
        scanf("%s",s+1);
        for(j=1;j<=m;++j)map[i][j]=hash(s[j]);
    }
     
    int x,y;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            if(map[i][j]==2)
                x=i,y=j;
     
    int id=0;
    map[x][y]=0;
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
            if((((getdis(i,x)+getdis(j,y))%2)^map[i][j])==0)
                lab[i][j]=++id;
     
    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)if(lab[i][j]){
            if(lab[i-1][j])addedge(lab[i][j],lab[i-1][j]);
            if(lab[i+1][j])addedge(lab[i][j],lab[i+1][j]);
            if(lab[i][j-1])addedge(lab[i][j],lab[i][j-1]);
            if(lab[i][j+1])addedge(lab[i][j],lab[i][j+1]);
        }
     
    for(i=1;i<=id;++i)
        if(!ano[i])memset(changed,0,sizeof changed),dfs(i);
 
    int steps;
    scanf("%d",&steps);
    steps<<=1;
    for(i=1;i<=steps;++i){
        if(ano[lab[x][y]]){
            int t=ano[lab[x][y]];
            ano[lab[x][y]]=ano[t]=0;
            del[lab[x][y]]=1;
            memset(changed,0,sizeof changed);
            win[i]=!dfs(t);
        }
        else{
            del[lab[x][y]]=1;
            win[i]=0;
        }
        scanf("%d%d",&x,&y);
    }
     
    int re=0;
    for(i=1;i<=steps;i+=2){
        if(win[i]&&win[i+1])++re;
    }
    printf("%d\n",re);
    for(i=1;i<=steps;i+=2){
        if(win[i]&&win[i+1])
            printf("%d\n",(i+1)>>1);
    }
    return 0;
}