【二分图博弈】LOJ6033 「雅礼集训 2017 Day2」棋盘游戏

题面在这里

​

显然可以把整个图黑白染色，得到一个二分图

考虑二分图最大匹配，如果初始点是未匹配点，则Bob只能走未匹配边到一个匹配点，而Alice一定可以沿匹配边走回左边的匹配点，由于不能往回走，此时的情形与初始状态一样，最终Bob输

如果初始点是匹配点，此时Bob走的是匹配边，Alice走未匹配边，如果最后能走回左边则Alice赢，否则Bob赢。其实他们走的是增广路，Alice能赢当且仅当初始点不一定是匹配点

所以答案是所有【不一定是匹配点】的点

具体做法是从左边未匹配点出发，沿增广路遍历到的所有左边点都是答案

​

示例程序：

#include<cstdio>
#include<cstring>
#define cl(x,y) memset(x,y,sizeof(x))

const int maxn=10005,maxe=40005,p[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int n,m,N,id[105][105];
char a[105][105];
int tot,son[maxe],lnk[maxn],nxt[maxe];
inline void add(int x,int y){
	son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;
}
int vis[maxn],times,con[maxn];
bool fnd(int x){
	if (vis[x]==times) return 0;
	vis[x]=times;
	for (int j=lnk[x];j;j=nxt[j]){
		int k=con[son[j]];con[son[j]]=x;
		if (!k||fnd(k)) return 1;
		con[son[j]]=k;
	}
	return 0;
}
bool ans[maxn][maxn];
void dfs(int x){
	vis[x]=1;
	for (int j=lnk[x];j;j=nxt[j])
	 if (!vis[con[son[j]]]) dfs(con[son[j]]);
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%s",a[i]+1);
	for (int i=1;i<=n;i++)
	 for (int j=1;j<=m;j++)
	  if (a[i][j]=='.') id[i][j]=++N;
	for (int i=1;i<=n;i++)
	 for (int j=1;j<=m;j++) if (a[i][j]=='.')
	  for (int t=0;t<4;t++){
	  	int ii=i+p[t][0],jj=j+p[t][1];
	  	if (ii<1||jj<1||ii>n||jj>m||a[ii][jj]=='#') continue;
	  	add(id[i][j],id[ii][jj]);
	  }
	int num=0;
	for (int i=1;i<=n;i++)
	 for (int j=1;j<=m;j++)
	  if (a[i][j]=='.'&&((i+j)&1)) times++,num+=fnd(id[i][j]);
	if (num*2==N) return puts("0"),0;
	for (int i=1;i<=N;i++) con[con[i]]=i;
	
	cl(vis,0);
	for (int i=1;i<=n;i++)
	 for (int j=1;j<=m;j++)
	  if (a[i][j]=='.'&&!vis[id[i][j]])
	  if (!con[id[i][j]]) dfs(id[i][j]);
	int ANS=0;
	for (int i=1;i<=n;i++)
	 for (int j=1;j<=m;j++)
	  if (vis[id[i][j]]) ANS++,ans[i][j]=1;
	
	printf("%d\n",ANS);
	for (int i=1;i<=n;i++)
	 for (int j=1;j<=m;j++)
	  if (ans[i][j]) printf("%d %d\n",i,j);
	return 0;
}