【算法】博弈论+二分图匹配(最大流)
【题解】方格图黑白染色得到二分图，
二分图博弈：当起点不属于某个最大匹配时，后手必胜。
问题转化为那些点不属于某个最大匹配。
先找到一个最大匹配，非匹配点加入答案。
假设一个匹配点要解放成为非匹配点，则与其匹配的点必须去匹配另一个点。如果另一个点也是匹配点，则其对面又要去找另一个点。
最终得到结论，一个匹配点的解放，必须有一个非匹配点进入最大匹配。
那么从S一侧的非匹配点出发，沿着“非匹配边-匹配边”的路径走，途中经过的S一侧的匹配点都可以被解放出来。
从T一侧的非匹配点出发也做一次，得到答案。
#include<cstdio> #include<cstring> #include<queue> #include<algorithm> using namespace std; const int maxn=10010,inf=0x3f3f3f3f; const int dx[]={0,-1,1,0,0}; const int dy[]={0,0,0,1,-1}; struct edge{int v,from,flow;}e[maxn*10]; int first[maxn],id[110][110],idx[maxn],idy[maxn],S,T,cnt,tot=1,d[maxn],ans[maxn],ansnum,cur[maxn],col[maxn],n,m; char s[110]; bool map[110][110],vis[maxn]; void insert(int u,int v,int w) {tot++;e[tot].v=v;e[tot].flow=w;e[tot].from=first[u];first[u]=tot; tot++;e[tot].v=u;e[tot].flow=0;e[tot].from=first[v];first[v]=tot;} queue<int>q; bool bfs() { memset(d,-1,sizeof(d)); q.push(S);d[S]=0; while(!q.empty()) { int x=q.front();q.pop(); for(int i=first[x];i;i=e[i].from) if(d[e[i].v]==-1&&e[i].flow) { d[e[i].v]=d[x]+1; q.push(e[i].v); } } return d[T]!=-1; } int dinic(int x,int a) { if(x==T||a==0)return a; int flow=0,f; for(int& i=cur[x];i;i=e[i].from) if(d[e[i].v]==d[x]+1&&(f=dinic(e[i].v,min(a,e[i].flow)))) { e[i].flow-=f; e[i^1].flow+=f; a-=f; flow+=f; if(a==0)break; } return flow; } void dfs(int x,int f) { vis[x]=1; if(col[x]==f&&x!=S&&x!=T)ans[++ansnum]=x; for(int i=first[x];i;i=e[i].from) if(e[i].flow==f&&!vis[e[i].v])dfs(e[i].v,f); } int main() { scanf("%d%d",&n,&m); cnt=0; for(int i=1;i<=n;i++) { scanf("%s",s+1); for(int j=1;j<=m;j++)if(s[j]=='.') { id[i][j]=++cnt; idx[cnt]=i;idy[cnt]=j; map[i][j]=1; } } S=0;T=++cnt; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++)if(map[i][j]) { if((i+j)&1) { insert(S,id[i][j],1); for(int k=1;k<=4;k++)if(map[i+dx[k]][j+dy[k]]) { insert(id[i][j],id[i+dx[k]][j+dy[k]],1); } col[id[i][j]]=1; } else{insert(id[i][j],T,1);col[id[i][j]]=0;} } } while(bfs()) { for(int i=0;i<=cnt;i++)cur[i]=first[i]; dinic(S,inf); } ansnum=0; memset(vis,0,sizeof(vis)); dfs(S,1); memset(vis,0,sizeof(vis)); dfs(T,0); if(ansnum) { printf("WIN "); sort(ans+1,ans+ansnum+1); for(int i=1;i<=ansnum;i++)printf("%d %d ",idx[ans[i]],idy[ans[i]]); } else printf("LOSE "); return 0; }