「雅礼集训 2017 Day2」棋盘游戏

祝各位圣诞后快乐（逃）

题目传送门

分析：

首先棋盘上的路径构成的图是一张二分图

那么对于一个二分图，先求出最大匹配，先手如果走到关键匹配点，只要后手顺着匹配边走，由于不再会出现增广路径，所以走到最后先手就必败

所以Alice只要到非关键匹配点，Bob便一定会走到关键匹配点，然后Alice便必胜

于是求一下那些点是非关键匹配点就好了

真难想233

我好菜233

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<map>

#include<queue>

#define maxn 500005

#define maxm 105

#define INF 0x3f3f3f3f

using namespace std;

inline long long getint()

{

    long long num=,flag=;char c;

    while((c=getchar())<''||c>'')if(c=='-')flag=-;

    while(c>=''&&c<='')num=num*+c-,c=getchar();

    return num*flag;

}

int n,m;

int S,T;

int fir[maxn],nxt[maxn],to[maxn],cap[maxn],cnt;

int h[maxn],vis[maxn];

char s[maxm][maxm];

int ans[maxm][maxm];

inline void newnode(int u,int v,int w)

{to[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt,cap[cnt]=w;}

inline void insert(int u,int v,int w)

{newnode(u,v,w),newnode(v,u,);}

inline bool bfs()

{

    memset(h,-,sizeof h);h[S]=;

    queue<int>Q;Q.push(S);

    while(!Q.empty())

    {

        int u=Q.front();Q.pop();

        for(int i=fir[u];i;i=nxt[i])

            if(!~h[to[i]]&&cap[i])h[to[i]]=h[u]+,Q.push(to[i]);

    }

    return ~h[T];

}

inline int aug(int u,int flow)

{

    if(u==T||!flow)return flow;

    int used=;

    for(int i=fir[u];i;i=nxt[i])

        if(cap[i]&&h[to[i]]==h[u]+)

        {

            int delta=aug(to[i],min(flow-used,cap[i]));

            cap[i]-=delta,cap[i^]+=delta,used+=delta;

            if(used==flow)return flow;

        }

    if(!used)h[u]=-;

    return used;

}

inline int dinic()

{

    int num=;

    while(bfs())num+=aug(S,INF);

    return num;

}

inline void dfs(int u)

{

    vis[u]=;

    for(int i=fir[u];i;i=nxt[i])if(!vis[to[i]]&&cap[i])dfs(to[i]);

}

inline void dfs2(int u)

{

    vis[u]=;

    for(int i=fir[u];i;i=nxt[i])if(!vis[to[i]]&&cap[i^])dfs2(to[i]);

}

inline int getid(int i,int j){return i*m+j-m;}

int main()

{

    n=getint(),m=getint();int num=;

    for(int i=;i<=n;i++)scanf("%s",s[i]+);

    S=n*m+,T=S+;cnt=;

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

    {

        if(((i+j)&)&&s[i][j]=='.')

        {

            insert(S,getid(i,j),);

            if(s[i-][j]=='.')insert(getid(i,j),getid(i-,j),INF);

            if(s[i+][j]=='.')insert(getid(i,j),getid(i+,j),INF);

            if(s[i][j-]=='.')insert(getid(i,j),getid(i,j-),INF);

            if(s[i][j+]=='.')insert(getid(i,j),getid(i,j+),INF);

        }

        if(!((i+j)&)&&s[i][j]=='.')insert(getid(i,j),T,);

    }

    dinic();

    dfs(S);

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

        if(((i+j)&)&&s[i][j]=='.'&&vis[getid(i,j)])ans[i][j]=,num++;

    memset(vis,,sizeof vis);

    dfs2(T);

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

        if(!((i+j)&)&&s[i][j]=='.'&&vis[getid(i,j)])ans[i][j]=,num++;

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

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

        if(ans[i][j])printf("%d %d\n",i,j);

}