首页 > 代码库 > 博弈论（二分图匹配）：NOI 2011 兔兔与蛋蛋游戏
博弈论（二分图匹配）：NOI 2011 兔兔与蛋蛋游戏
Description
Input
输入的第一行包含两个正整数 n、m。
接下来 n行描述初始棋盘。其中第i 行包含 m个字符，每个字符都是大写英文字母"X"、大写英文字母"O"或点号"."之一，分别表示对应的棋盘格中有黑色棋子、有白色棋子和没有棋子。其中点号"."恰好出现一次。
接下来一行包含一个整数 k（1≤k≤1000） ，表示兔兔和蛋蛋各进行了k次操作。
接下来 2k行描述一局游戏的过程。其中第 2i – 1行是兔兔的第 i 次操作（编号为i的操作） ，第2i行是蛋蛋的第i次操作。每个操作使用两个整数x,y来描述，表示将第x行第y列中的棋子移进空格中。
输入保证整个棋盘中只有一个格子没有棋子， 游戏过程中兔兔和蛋蛋的每个操作都是合法的，且最后蛋蛋获胜。
Output
输出文件的第一行包含一个整数r，表示兔兔犯错误的总次数。
接下来r 行按递增的顺序给出兔兔“犯错误”的操作编号。其中第 i 行包含一个整数ai表示兔兔第i 个犯错误的操作是他在游戏中的第 ai次操作。
1 ≤n≤ 40， 1 ≤m≤ 40
Sample Input
1 6
XO.OXO
1
1 2
1 1
样例二：
3 3
XOX
O.O
XOX
4
2 3
1 3
1 2
1 1
2 1
3 1
3 2
3 3
样例三：
4 4
OOXX
OXXO
OO.O
XXXO
2
3 2
2 2
1 2
1 3
Sample Output
1
1
样例二：
0
样例三：
2
1
2
样例1对应图一中的游戏过程
样例2对应图三中的游戏过程
HINT
这道题很好，思维巧妙又不难打。题解直接引用maijing的：
二分图匹配。
性质1 空格移动的路径一定不会自交。
记出发格子为A_0，第i步到达的格子为A_i。
虽然第一次相交的点不一定是A_0，但不失一般性，假设走了n步之后第一次与A_0相交，即走过了A_0,A_1,A_2,...,A_n-1,A_n。
因为每次是移动是上下左右四个方向之一，因为又回到出发点，所以有多少次向上走就有多少次向下走，有多少次向左走就有多少次向右走，所以n是偶数。
我们发现，第奇数次移动的为先手，即A_1,A_3,A_5,...,A_n-1；第偶数次移动的为后手，即A_0,A_2,A_4,...,A_n。
因为又回到了出发地，所以A_1和A_n是同一个棋子，但是2个人同时移动了这个棋子，矛盾，所以空格移动的路径一定不会自交。
不妨将刚开始时空格所在的格子看成黑色 那么空格移动的路径一定是黑白相间的。
建立二分图，左边为黑色，右边为白色，之间有相邻关系的连边。兔兔是从左边走到右边，蛋蛋是从右边走到左边。
性质2 当且仅当最大匹配一定覆盖空格所在的结点时，兔兔必胜；否则蛋蛋必胜。
（1）如果存在一个最大匹配不覆盖空格所在的结点，蛋蛋必胜。
如图实线是匹配边，虚线是非匹配边，空格所在的结点为start。
因为最大匹配不覆盖空格所在的结点start，所以兔兔只能沿着某一条非匹配边到右边，不妨设到了v（如果没有到右边的没走过的非匹配边，那么兔兔输了）。
v一定是被覆盖的（不然start就可以连到v，就不是最大匹配了）。
蛋蛋可以沿着覆盖v的匹配边到左边的u。
也就是说，当兔兔到了右边后，蛋蛋一定有路径回到左边；但是当蛋蛋到了左边后，兔兔不一定有路径到右边。
所以如果存在一个最大匹配不覆盖空格所在的结点，蛋蛋必胜。
（2）如果最大匹配一定覆盖空格所在的结点时，兔兔必胜。
我们可以类似（1）中进行分析。
虽然这道题不是问我们谁必胜，但这给我们接下来提供了一种思考方法。
现在兔兔走第1步，从start走到v。
首先我们根据性质2，判断兔兔是否必胜，就是判断使用start点和不使用start点时的最大匹配是否相等，如果不相等，说明最大匹配一定覆盖start点，兔兔必胜。
然后强行覆盖start到v的边。
我们要这时候蛋蛋要从左边往右边走，我们要判断蛋蛋是否必胜。
如果蛋蛋能够走到兔兔的一个必败态，那么蛋蛋必胜。
根据性质2，我们得出结论：在start到v的边一定被覆盖的情况下，当且仅当与v有边相连的所有点都一定被最大匹配覆盖，蛋蛋必输；否则蛋蛋必胜。
所以如果在某种最大匹配方案中，与v相连的某个点没有被最大匹配覆盖，那么蛋蛋必胜。
如图，与v相连的点为a,b,c，在图示的最大匹配方案中，c没有被最大匹配覆盖，所以蛋蛋必胜。
接下来读入蛋蛋第1步走的格子，start变成为蛋蛋第1步走的格子。
然后类似做就可以了。
然后代码极简单。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 const int N=1610; 6 const int M=15010; 7 int cnt,cntX,cntO; 8 int fir[N],to[M],nxt[M]; 9 int match[N],vis[N],ban[N],id[50][50],ans[100010];10 char map[50][50];11 int n,m,px,py;12 int tx[4]={0,1,0,-1};13 int ty[4]={1,0,-1,0};14 void addedge(int a,int b){15 nxt[++cnt]=fir[a];to[fir[a]=cnt]=b;16 }17 18 bool DFS(int x){19 for(int i=fir[x];i;i=nxt[i])20 if(!vis[to[i]]&&!ban[to[i]]){vis[to[i]]=1;21 if(!match[to[i]]||DFS(match[to[i]]))22 {match[match[to[i]]=x]=to[i];return true;}23 }24 return false; 25 }26 27 int main(){28 scanf("%d%d",&n,&m);29 for(int i=1;i<=n;i++)30 scanf("%s",map[i]+1);31 for(int i=1;i<=n;i++)32 for(int j=1;j<=m;j++){33 if(map[i][j]==‘.‘)34 map[i][j]=‘X‘,px=i,py=j;35 if(map[i][j]==‘O‘)36 id[i][j]=++cntO;37 else if(map[i][j]==‘X‘)38 id[i][j]=++cntX; 39 }40 for(int i=1;i<=n;i++)41 for(int j=1;j<=m;j++)42 if(map[i][j]==‘O‘)43 id[i][j]+=cntX;44 45 for(int i=1;i<=n;i++)46 for(int j=1;j<=m;j++)if(id[i][j]){47 for(int k=0;k<4;k++){48 int gx=tx[k]+i,gy=ty[k]+j;49 if(map[gx][gy]!=map[i][j])50 addedge(id[i][j],id[gx][gy]);51 }52 }53 for(int i=1;i<=cntX;i++)if(!match[i])54 {memset(vis,0,sizeof(vis));DFS(i);}55 56 int k;scanf("%d",&k);57 for(int i=1;i<=2*k;i++){58 int x;ban[x=id[px][py]]=1;59 if(match[x]){int y=match[x];60 memset(vis,0,sizeof(vis));61 match[x]=match[y]=0;62 ans[i]=DFS(y)^1;63 }64 scanf("%d%d",&px,&py);65 }66 int ret=0;67 for(int i=1;i<=k;i++)68 ret+=ans[i*2]&ans[i*2-1];69 printf("%d\n",ret);70 for(int i=1;i<=k;i++)71 if(ans[i*2]&ans[i*2-1])72 printf("%d\n",i);73 return 0;74 }
博弈论（二分图匹配）：NOI 2011 兔兔与蛋蛋游戏