$n \leq 100$,$m \leq 100$的$n*m$地图，现进行一个博弈：后手先选个点放棋子，然后先后手轮流向上下左右某个方向移动棋子一步，不能移到障碍点，一个非障碍点不能走两次。问所有后手能赢的位置。
可以发现网格图是一个二分图，在移动时好像在二分图的两边反复横跳。可以在二分图这个模型上进行尝试，比如说，求最大匹配，看一下匹配点和非匹配点的情况。
从匹配点开始：（不如把放棋子那人叫B）
A如果走了一条匹配边，那B可以随意走一步，这一步一定是非匹配边，然后轮到A：1、如果A又走了一条匹配边，回到刚才情况；2、A没走匹配边，那情况就反转了，因为连走两条非匹配边一定会走到一个匹配点。等等蛤，B为啥一定可以随意走一步？陷入江局。。
从非匹配点开始：
A会走一条非匹配边到一个匹配点，然后B只要走最大匹配即可，因为A每一步都只能走非匹配边到另一个匹配点（如果不是匹配点，那他们走过的路就可以增广，不符合最大匹配）。这样A输定。
也就是说，只要选择不出现在某一个最大匹配的点，就一定赢。
直接一次最大匹配算法只能求一个最大匹配，没匹配的点一定是答案。但是，只要在最大匹配算法结束后，从S集的点沿着非匹配边-匹配边走到另外的S集点，这些“另外的点”也是答案，因为走过的路径相当于做了一次没损失没收益的增广，依然是最大匹配。同理，T集的点沿着非匹配边-匹配边走到的T集点也是答案。
我用的Dinic求最大匹配，所以就看S能到达哪些S集点以及哪些T集点能到T即可。
?1 //#include<iostream> ?2 #include<cstring> ?3 #include<cstdlib> ?4 #include<cstdio> ?5 //#include<queue> ?6 //#include<time.h> ?7 //#include<complex> ?8 #include<algorithm> ?9 #include<stdlib.h> 10 using namespace std; 11 ?12 int n,m; 13 #define maxn 10011 14 #define maxm 100011 15 ?16 bool vis[111][111]; int col[maxn],id[111][111],tot; 17 int qx[maxn],qy[maxn],head,tail; 18 const int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; 19 bool mp[111][111]; char s[111]; 20 void bfs(int sx,int sy) 21 { 22 ????head=0; tail=1; qx[0]=sx; qy[0]=sy; 23 ????col[id[sx][sy]]=1; vis[sx][sy]=1; 24 ????while (head!=tail) 25 ????{ 26 ????????int nx=qx[head],ny=qy[head]; head++; 27 ????????for (int i=0;i<4;i++) 28 ????????{ 29 ????????????int xx=nx+dx[i],yy=ny+dy[i]; 30 ????????????if (xx<1 || xx>n || yy<1 || yy>m || !mp[xx][yy] || vis[xx][yy]) continue; 31 ????????????vis[xx][yy]=1; col[id[xx][yy]]=-col[id[nx][ny]]; 32 ????????????qx[tail]=xx; qy[tail]=yy; tail++; 33 ????????} 34 ????} 35 } 36 ?37 struct Edge{int from,to,cap,flow,next;}; 38 struct Network 39 { 40 ????Edge edge[maxm]; int first[maxn],le,n; 41 ????Network() {le=2;} 42 ????void in(int x,int y,int cap) {Edge &e=edge[le]; e.from=x; e.to=y; e.cap=cap; e.flow=0; e.next=first[x]; first[x]=le++;} 43 ????void insert(int x,int y,int cap) {in(x,y,cap); in(y,x,0);} 44 ????int dis[maxn],s,t,que[maxn],head,tail,cur[maxn]; 45 ????bool bfs() 46 ????{ 47 ????????for (int i=1;i<=n;i++) dis[i]=0x3f3f3f3f; dis[s]=0; 48 ????????head=0; tail=1; que[0]=s; 49 ????????while (head!=tail) 50 ????????{ 51 ????????????int now=que[head++]; 52 ????????????for (int i=first[now];i;i=edge[i].next) 53 ????????????{ 54 ????????????????Edge &e=edge[i]; 55 ????????????????if (e.cap>e.flow && dis[e.to]==0x3f3f3f3f) 56 ????????????????{ 57 ????????????????????dis[e.to]=dis[now]+1; 58 ????????????????????que[tail++]=e.to; 59 ????????????????} 60 ????????????} 61 ????????} 62 ????????return dis[t]!=0x3f3f3f3f; 63 ????} 64 ????int dfs(int x,int a) 65 ????{ 66 ????????if (x==t || !a) return a; 67 ????????int flow=0,f; 68 ????????for (int &i=cur[x];i;i=edge[i].next) 69 ????????{ 70 ????????????Edge &e=edge[i]; 71 ????????????if (dis[e.to]==dis[x]+1 && (f=dfs(e.to,min(a,e.cap-e.flow)))>0) 72 ????????????{ 73 ????????????????flow+=f; e.flow+=f; 74 ????????????????edge[i^1].flow-=f; a-=f; 75 ????????????????if (!a) return flow; 76 ????????????} 77 ????????} 78 ????????return flow; 79 ????} 80 ????int Dinic(int s,int t) 81 ????{ 82 ????????this->s=s; this->t=t; 83 ????????int ans=0; 84 ????????while (bfs()) 85 ????????{ 86 ????????????for (int i=1;i<=n;i++) cur[i]=first[i]; 87 ????????????ans+=dfs(s,0x3f3f3f3f); 88 ????????} 89 ????????return ans; 90 ????} 91 ????bool vis[maxn],v2[maxn]; 92 ????void solve() 93 ????{ 94 ????????head=0; tail=1; que[0]=s; 95 ????????memset(v2,0,sizeof(v2)); v2[s]=1; 96 ????????while (head!=tail) 97 ????????{ 98 ????????????int now=que[head++]; if (col[now]==1) vis[now]=1; 99 ????????????for (int i=first[now];i;i=edge[i].next)100 ????????????{101 ????????????????Edge &e=edge[i]; if (v2[e.to] || e.to==t || e.cap<=e.flow) continue;102 ????????????????que[tail++]=e.to,v2[e.to]=1;103 ????????????}104 ????????}105 ????????head=0; tail=1; que[0]=t;106 ????????memset(v2,0,sizeof(v2)); v2[t]=1;107 ????????while (head!=tail)108 ????????{109 ????????????int now=que[head++]; if (col[now]==-1) vis[now]=1;110 ????????????for (int i=first[now];i;i=edge[i].next)111 ????????????{112 ????????????????Edge &e=edge[i]; if (v2[e.to] || e.to==s) continue;113 ????????????????if (e.cap==e.flow) que[tail++]=e.to,v2[e.to]=1;114 ????????????}115 ????????}116 ????}117 }g;118 119 int main()120 {121 ????scanf("%d%d",&n,&m);122 ????for (int i=1;i<=n;i++)123 ????{124 ????????scanf("%s",s+1);125 ????????for (int j=1;j<=m;j++) mp[i][j]=(s[j]==‘.‘);126 ????}127 ????for (int i=1;i<=n;i++)128 ????????for (int j=1;j<=m;j++) if (mp[i][j])129 ????????????id[i][j]=++tot;130 ????for (int i=1;i<=n;i++)131 ????????for (int j=1;j<=m;j++)132 ????????????if (mp[i][j] && !vis[i][j]) bfs(i,j);133 ????int s=tot+1,t=s+1; g.n=t;134 ????for (int i=1;i<=n;i++)135 ????????for (int j=1;j<=m;j++) if (mp[i][j])136 ????????????for (int k=0;k<4;k+=2)137 ????????????{138 ????????????????int xx=i+dx[k],yy=j+dy[k];139 ????????????????if (xx<1 || xx>n || yy<1 || yy>m || mp[xx][yy]==0) continue;140 ????????????????if (col[id[i][j]]==1) g.insert(id[i][j],id[xx][yy],1);141 ????????????????else g.insert(id[xx][yy],id[i][j],1);142 ????????????}143 ????for (int i=1;i<=n;i++)144 ????????for (int j=1;j<=m;j++) if (mp[i][j])145 ????????{146 ????????????if (col[id[i][j]]==1) g.insert(s,id[i][j],1);147 ????????????else g.insert(id[i][j],t,1);148 ????????}149 ????g.Dinic(s,t);150 ????g.solve();151 ????bool flag=0;152 ????for (int i=1;i<=n;i++)153 ????????for (int j=1;j<=m;j++)154 ????????????if (g.vis[id[i][j]])155 ????????????{156 ????????????????if (!flag) {flag=1; puts("WIN");}157 ????????????????printf("%d %d\n",i,j);158 ????????????}159 ????if (!flag) puts("LOSE");160 ????return 0;161 }BZOJ1443: [JSOI2009]游戏Game
原文地址：https://www.cnblogs.com/Blue233333/p/8570449.html