BZOJ2437 NOI2011兔兔与蛋蛋（二分图匹配+博弈）

时间：2023-03-10 01:06:31
BZOJ2437 NOI2011兔兔与蛋蛋（二分图匹配+博弈）

　　首先将棋盘黑白染色，不妨令空格处为黑色。那么移动奇数次后空格一定处于白色格子，偶数次后空格一定处于黑色格子。所以若有某个格子的棋子颜色与棋盘颜色不同，这个棋子就是没有用的。并且空格与某棋子交换后，棋子所在的格子改变使得该棋子与棋盘颜色不同，那么该棋子也会变为无用棋子。那么问题变为空格在棋盘上黑白格子交替移动，棋盘上有障碍物，走过的格子不能再走，不能移动者输。

　　显然这是一个二分图博弈。如果所有的最大匹配都包含起点，先手必胜，因为每次只需要沿匹配边走即可，由增广路定理不会出现没边走的情况。否则后手必胜，因为一旦起点不在最大匹配中，走了一条边后后手变成先手，所达点一定在（不包含起点的）最大匹配中。那么每次我们只需要判断空格位置是否处于剩余图的所有最大匹配中，也即判断删除该点后最大匹配是否会减少。这只需要从被删除点原本的匹配点出发找增广路。判断完每次操作后是否处于必胜态后只要看是否从必胜态走到了必胜态即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 42

char getc(){char c=getchar();while (c==||c==||c==) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,k,X,Y,a[N][N],p[N*N],match[N*N],id[N][N],cnt,t,ans;

bool flag[N*N],tag[N*N],win[];

int wx[]={,,,-},wy[]={,-,,};

struct data{int to,nxt;

}edge[N*N<<];

void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}

bool hungary(int k)

{

    for (int i=p[k];i;i=edge[i].nxt)

    if (!flag[edge[i].to]&&!tag[edge[i].to])

    {

        int x=edge[i].to;

        flag[x]=;

        if (!match[x]||!tag[match[x]]&&hungary(match[x]))

        {

            match[x]=k,match[k]=x;

            return ;

        }

    }

    return ;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj2437.in","r",stdin);

    freopen("bzoj2437.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();

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

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

        {

            char c=getc();

            a[i][j]=c=='O';

            if (c=='.') X=i,Y=j;

        }

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

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

            for (int k=;k<;k++)

            if (i+wx[k]>=&&i+wx[k]<=n&&j+wy[k]>=&&j+wy[k]<=m&&

            (abs(i-X)+abs(j-Y)&)==a[i][j]&&(abs(i+wx[k]-X)+abs(j+wy[k]-Y)&)==a[i+wx[k]][j+wy[k]])

            {

                if (!id[i][j]) id[i][j]=++cnt;if (!id[i+wx[k]][j+wy[k]]) id[i+wx[k]][j+wy[k]]=++cnt;

                addedge(id[i][j],id[i+wx[k]][j+wy[k]]),addedge(id[i+wx[k]][j+wy[k]],id[i][j]);

            }

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

    if (!match[i]) memset(flag,,sizeof(flag)),hungary(i);

    tag[id[X][Y]]=;

    if (match[id[X][Y]])

    {

        memset(flag,,sizeof(flag));

        match[match[id[X][Y]]]=;

        win[]=!hungary(match[id[X][Y]]);

    }

    int k=read()<<;

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

    {

        int x=read(),y=read();

        tag[id[x][y]]=;

        if (match[id[x][y]])

        {

            memset(flag,,sizeof(flag));

            match[match[id[x][y]]]=;

            win[i]=!hungary(match[id[x][y]]);

        }

    }

    int tot=;

    for (int i=;i<k;i+=) if (win[i]&&win[i+]) tot++;

    cout<<tot<<endl;

    for (int i=;i<k;i+=) if (win[i]&&win[i+]) printf("%d\n",(i>>)+);

    return ;

}

相关文章