题目
给个有障碍物的(n imes m)棋盘，两个人轮流移动棋子，一个格子只能经过一次，不能移动的人算输；先手可以任选一个起点然后移动一格，问先手有多少个必胜的选法
思路
一人一步的东西，不是博弈论就是二分图了吧。。。毕竟上次被兔兔和蛋蛋坑了还是要记住的
按照套路，对棋盘黑白染色；对二分图求最大匹配，如果该二分图不存在完备匹配，那么先手必输，否则所有可能成为非匹配点的点都可以作为起点
因为从非匹配点出发，先手选择走匹配边走到一个匹配点，之后的路径就是走最大匹配的路径了，因为是偶数个点，所以最后一定是后手无路可走，可以证明一定后手无法走出这个最大匹配的路径，否则就会形成一条増广路
跑个网络流，用个DFS跑出所有非匹配点就行了，这个DFS类似求増广路的过程，具体见代码
Code
#include<bits/stdc++.h>
#define N 20005
#define Min(x,y) ((x)<(y)?(x):(y))
#define Max(x,y) ((x)>(y)?(x):(y))
using namespace std;
const int inf = 10000000;
int n,m,s,t;
int a[105][105];
int dox[4]={0,1,0,-1},doy[4]={1,0,-1,0};
int dep[N],pp[N],up[N];
char c[105];
bool vis[N],lef[N];
struct Edge
{
int next,to,flow;
}edge[N<<3];int head[N],cur[N],cnt=1;
void add_edge(int from,int to,int flow)
{
edge[++cnt].next=head[from];
edge[cnt].to=to;
edge[cnt].flow=flow;
head[from]=cnt;
}
void add(int from,int to,int flow)
{
add_edge(from,to,flow);
add_edge(to,from,0);
}
int id(int x,int y) {return (x-1)*m+y;}
bool bfs()
{
memset(dep,0,sizeof(dep));
queue<int> q;
dep[s]=1; q.push(s);
while(!q.empty())
{
int u=q.front(); q.pop();
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(dep[v]||edge[i].flow<=0) continue;
dep[v]=dep[u]+1;
q.push(v);
if(v==t) return true;
}
}
return false;
}
int dfs(int rt,int rest)
{
if(rt==t) return rest;
int used=0;
for(int i=head[rt];i&&used<=rest;i=edge[i].next)
{
int v=edge[i].to;
if(dep[v]==dep[rt]+1&&edge[i].flow)
{
int k=dfs(v,Min(rest-used,edge[i].flow));
if(!k) dep[v]=0;
edge[i].flow-=k;
edge[i^1].flow+=k;
used+=k;
}
}
return used;
}
int dinic()
{
int ret=0;
while(bfs()) ret+=dfs(s,inf);
return ret;
}
void DFS(int rt,int lim)
{
if(vis[rt]) return;
vis[rt]=1;
if(lef[rt]==lim) pp[rt]=1;
for(int i=head[rt];i;i=edge[i].next) if(edge[i].flow==lim) DFS(edge[i].to,lim);
}
int main()
{
scanf("%d%d",&n,&m);
s=0;t=n*m+1;
for(int i=1;i<=n;++i)
{
scanf("%s",c);
for(int j=1;j<=m;++j) a[i][j]=(c[j-1]=='.');
}
int sum=0;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
if(a[i][j])
{
++sum;
int fr=id(i,j);
if((i+j)%2) add(s,fr,1),lef[fr]=1;
else add(fr,t,1);
if((i+j)%2)
for(int k=0;k<4;++k)
{
int dx=dox[k]+i,dy=doy[k]+j;
if(dx<1||dy<1||dx>n||dy>m||!a[dx][dy]) continue;
int to=id(dx,dy);
add(fr,to,1);
}
}
}
}
int ans=dinic()*2;
if(sum==ans) { puts("LOSE"); return 0; }
puts("WIN");
DFS(s,1);
memset(vis,0,sizeof(vis));
DFS(t,0);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(pp[id(i,j)]&&a[i][j]) printf("%d %d
",i,j);
return 0;
}