BZOJ1443: [JSOI2009]游戏Game 二分图+博弈论+网络流

思路:

首先将图黑白二染色变成二分图.

然后求出一组最大匹配.

如果某个点不在匹配中,那么先手选择这个点.

那么后手只能走向一个匹配点(否则就不是最大匹配了).于是先手就可以沿着匹配边走回来.

那么此时如果后手还能走的话,就必定走到一个匹配点上.(否则就存在增广路了).于是先手又沿着匹配边走回来.

最后总是后手无路可走.因此先手必胜.

因此如果某个点不是最大匹配的必须点.就可以选择这个点.

如何找出这个呢?

在残量网络上,从\(S\)出发能够遍历到的左端的点,以及从\(T\)出发能够反向遍历到的右端的点.

证明的话,就是如果能够遍历到,就证明可以被换掉,而使得匹配数不减少.(稍微脑补一下)

(注意总点数要开2W,我不知道为什么)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define INF ~0U>>1
struct Solver{
    static const int V=20010;
    static const int E=V<<2;
    int head[V],next[E],end[E],flow[E],ind;
    int gap[V],d[V],stk[V],top,cur[V];
    inline void reset(){
        ind=top=0,memset(head,-1,sizeof head);
    }
    inline void addedge(int a,int b,int f){
        int q=ind++;
        end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;
    }
    inline void make(int a,int b,int f){
        //printf("%d %d %d\n",a,b,f);
        addedge(a,b,f),addedge(b,a,0);
    }
    inline void bfs(int T){
        static int q[V];
        int fr=0,ta=0;
        memset(d,-1,sizeof d),memset(gap,0,sizeof gap),++gap[d[T]=0],q[ta++]=T;
        while(fr^ta){
            int i=q[fr++];
            for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)
                ++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
        }
    }
    inline int Maxflow(int S,int T){
        int re=0,ins,Min,i,u=S;
        bfs(T),memcpy(cur,head,sizeof cur);
        while(d[S]<T-S+1){
            if(u==T){
                for(Min=INF,i=0;i<top;++i)if(Min>flow[stk[i]])Min=flow[stk[i]],ins=i;
                for(re+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
                u=end[stk[top=ins]^1];
            }
            if(u!=T&&!gap[d[u]-1])break;
            bool find=0;
            for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]+1==d[u]){
                find=1,ins=j;break;
            }
            if(find){
                stk[top++]=cur[u]=ins,u=end[ins];
            }
            else{
                Min=T-S+1;
                for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)
                    cur[u]=j,Min=d[end[j]];
                if(!--gap[d[u]])break;
                ++gap[d[u]=Min+1];
                if(u!=S)u=end[stk[--top]^1];
            }
        }
        return re;
    }
}Stg;
 
#define N 110
char s[N];
int lab[N][N],x[N*N],y[N*N];
 
int res[N*N],nums;
 
bool vis[N*N];
inline void bfs(int S,bool rev){
    static int q[N*N];
    int fr=0,ta=0;
    memset(vis,0,sizeof vis),vis[S]=1,q[ta++]=S;
    while(fr^ta){
        int i=q[fr++];
        for(int j=Stg.head[i];j!=-1;j=Stg.next[j])if(Stg.flow[j^rev]&&!vis[Stg.end[j]])
            vis[Stg.end[j]]=1,q[ta++]=Stg.end[j];
    }
}
 
int main(){
    int n,m;scanf("%d%d",&n,&m);
    register int i,j;
    int cnt=0;
    for(i=1;i<=n;++i){
        scanf("%s",s+1);
        for(j=1;j<=m;++j)if(s[j]!='#')lab[i][j]=++cnt,x[cnt]=i,y[cnt]=j;
    }
     
    int S=0,T=cnt+1,num0=0,num1=0;
    Stg.reset();
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(lab[i][j]){
        if((i+j)&1){
            ++num1;
            Stg.make(S,lab[i][j],1);
            if(lab[i-1][j])Stg.make(lab[i][j],lab[i-1][j],INF);
            if(lab[i+1][j])Stg.make(lab[i][j],lab[i+1][j],INF);
            if(lab[i][j-1])Stg.make(lab[i][j],lab[i][j-1],INF);
            if(lab[i][j+1])Stg.make(lab[i][j],lab[i][j+1],INF);
        }
        else
            ++num0,Stg.make(lab[i][j],T,1);
    }
     
    if(num0==0&&num1==0){
        puts("LOSE");
        return 0;
    }
     
    int re=Stg.Maxflow(S,T);
     
    /*for(i=S;i<=T;++i)for(j=Stg.head[i];j!=-1;j=Stg.next[j])
        printf("%d %d %d\n",i,Stg.end[j],Stg.flow[j]);*/
    if(num0==num1&&re==num0){
        puts("LOSE");
        return 0;
    }
    puts("WIN");
     
    bfs(S,0);
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(lab[i][j]&&((i+j)&1)&&vis[lab[i][j]])res[++nums]=lab[i][j];
    bfs(T,1);
    for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(lab[i][j]&&((i+j)%2==0)&&vis[lab[i][j]])res[++nums]=lab[i][j];
    sort(res+1,res+nums+1);
     
    for(i=1;i<=nums;++i){
        printf("%d %d\n",x[res[i]],y[res[i]]);
    }
     
    return 0;
}