bzoj2437 [Noi2011]兔兔与蛋蛋

二分图博弈果然都是一个套路，必经点必胜，非必经点必败，

但是肯定不能每走一步就重新建图判断必胜还是必败，那么我们可以这样：每走一步就把这个点删掉，然后find他原来的匹配，如果找不到，就说明他是必经点，否则就是非必经点。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <cmath>

 #define N 1601

 using namespace std;

 int e=,head[N];

 struct edge{int v,next;}ed[N*];

 void add(int u,int v){ed[e].v=v;ed[e].next=head[u];head[u]=e++;}

 int pp[N],del[N],id[][];

 bool vis[N],ans[N];

 bool find(int x){

     for(int i=head[x];i;i=ed[i].next){

         int v=ed[i].v;

         if(del[v]||vis[v])continue;vis[v]=;

         if(!pp[v]||find(pp[v])){

             pp[v]=x;pp[x]=v;

             return ;

         }

     }return ;

 }

 int a[][],be,n,m,T,sx,sy,tot1,tot2,tot;

 char ch[];

 bool check(int i,int j){return ((i+j)&)^a[i][j]==be;}

 int f[N],f_cnt;

 int main(){

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++){

         scanf("%s",ch+);

         for(int j=;j<=m;j++)

             if(ch[j]=='O')a[i][j]=;

             else if(ch[j]=='X')a[i][j]=;

             else sx=i,sy=j;

     }

     be=(sx+sy)&;

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)if(check(i,j))

             if(a[i][j])id[i][j]=++tot1;

             else id[i][j]=++tot2;

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)if(check(i,j)&&(!a[i][j]))

             id[i][j]+=tot1;

     tot=tot1+tot2;

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)if(id[i][j]){

             if(id[i+][j])add(id[i][j],id[i+][j]);

             if(id[i][j+])add(id[i][j],id[i][j+]);

             if(id[i-][j])add(id[i][j],id[i-][j]);

             if(id[i][j-])add(id[i][j],id[i][j-]);

         }

     for(int i=;i<=tot1;i++){

         memset(vis,,sizeof vis);

         find(i);

     }

     scanf("%d",&T);T<<=;

     for(int i=,x,y;i<=T;i++){

         int now=id[sx][sy],p=pp[now];

         del[now]=;pp[now]=pp[p]=;

         if(!p)ans[i]=;

         else{

             memset(vis,,sizeof vis);

             ans[i]=find(p)^;

         }

         scanf("%d%d",&sx,&sy);

     }

     for(int i=;i<=T;i+=)

         if(ans[i]&&ans[i+])f[++f_cnt]=(i+)>>;

     printf("%d\n",f_cnt);

     for(int i=;i<=f_cnt;i++)

         printf("%d\n",f[i]);

     return ;

 }