bzoj1443 [JSOI2009]游戏Game
二分图上的博弈游戏。
我们把二分图上的点分成两类，一类是一定在最大匹配中的，一类是不一定在里面的。
如果我把棋子放到了必经点上，那么对手就可以一直走匹配边，我只能在找非匹配边，因为最大匹配没有增广路，所以我必输
那么反过来，我把棋子放到了非必经点上，我们可以发现对手无论怎么走，走到的都是必经点上，我就可以像上面他玩我一样玩他。
所以我们把棋子放到非必经点上必胜，否则必败
这是为什么呢，因为我们把棋子放到非必经点上，无论对手怎么走，我们一定能构造出一个包含该终点的最大匹配
我们尝试来证明一下。
我们考虑非必经点是怎么得到的，首先我们求出了一个最大匹配，那么不在这个最大匹配中的点一定是非必经点，我们从他出发的边一定指向的是最大匹配中的点（因为最大匹配没有增广路），这满足上面的黑体字，那么考虑另外的非必经点是怎么得到的，是从这些点沿着匹配边--非匹配边dfs出的，也就是说那些点是完全等价的，可以直接代替，这样就和前面一样了。
所以说我们只要考虑第一步怎么放，后边怎么走？管他呢！
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <cmath> 5 #include <algorithm> 6 #define N 10050 7 using namespace std; 8 int e=1,head[N]; 9 struct edge{int v,next;}ed[N<<3]; 10 void add(int u,int v){ed[e].v=v;ed[e].next=head[u];head[u]=e++;} 11 bool bo[N],vis[N],ans[N]; 12 int id[105][105],pp[N]; 13 bool find(int x){ 14 for(int i=head[x];i;i=ed[i].next){ 15 int v=ed[i].v; 16 if(bo[v])continue;bo[v]=1; 17 if(!pp[v]||find(pp[v])){ 18 pp[v]=x;pp[x]=v; 19 vis[v]=vis[x]=1; 20 return 1; 21 } 22 }return 0; 23 } 24 void dfs(int x,int o){ 25 bo[x]=1; 26 if(!o){ 27 for(int i=head[x];i;i=ed[i].next){ 28 int v=ed[i].v; 29 if(!bo[v])dfs(v,o^1); 30 }ans[x]=1; 31 } 32 else{dfs(pp[x],o^1);} 33 } 34 int n,m,tot,tot1,tot2,cnt; 35 char ch[105]; 36 int main(){ 37 scanf("%d%d",&n,&m); 38 for(int i=1;i<=n;i++){ 39 scanf("%s",ch+1); 40 for(int j=1;j<=m;j++)if(ch[j]=='.') 41 if((i+j)&1)id[i][j]=++tot1; 42 else id[i][j]=++tot2; 43 } 44 /*for(int i=1;i<=n;i++) 45 for(int j=1;j<=m;j++)if(id[i][j])printf("%d %d %d ",i,j,id[i][j]); 46 return 0;*/ 47 for(int i=1;i<=n;i++) 48 for(int j=1;j<=m;j++) 49 if(id[i][j]&&(!((i+j)&1)))id[i][j]+=tot1; 50 tot=tot1+tot2; 51 for(int i=1;i<n;i++) 52 for(int j=1;j<=m;j++) 53 if(id[i][j]&&id[i+1][j])add(id[i][j],id[i+1][j]),add(id[i+1][j],id[i][j]); 54 for(int i=1;i<=n;i++) 55 for(int j=1;j<m;j++) 56 if(id[i][j]&&id[i][j+1])add(id[i][j],id[i][j+1]),add(id[i][j+1],id[i][j]); 57 for(int i=1;i<=tot1;i++){ 58 memset(bo,0,sizeof bo); 59 if(find(i))cnt++; 60 } 61 if(tot==cnt*2){puts("LOSE");return 0;} 62 puts("WIN"); 63 for(int i=1;i<=tot;i++) 64 if(!vis[i]){ 65 memset(bo,0,sizeof bo); 66 dfs(i,0); 67 } 68 //for(int i=1;i<=n;i++) 69 //for(int j=1;j<=m;j++)if(id[i][j])printf("%d %d %d ",i,j,id[i][j]); 70 for(int i=1;i<=n;i++) 71 for(int j=1;j<=m;j++) 72 if(id[i][j]&&ans[id[i][j]])printf("%d %d ",i,j); 73 return 0; 74 }