【BZOJ2437】[NOI2011] 兔兔与蛋蛋(博弈论+二分图匹配)

点此看题面

大致题意: 一个\(n\times m\)的棋盘上,除一个格子为空之外,其余格子上都摆着黑色或白色的棋子。兔兔和蛋蛋轮流将空格旁边一个白色/黑色棋子移到空格上,谁先不能操作谁就输了。现在把他们的操作记录给你,让你判断兔兔哪几次操作是犯错误的(即该操作前兔兔有必胜策略,该操作后蛋蛋有必胜策略)。

前言

今天也做了好几道博弈论的题目了,做完这道题之后,彻底放弃了初步了解博弈论的幻想。

为什么呢?因为今天做到的博弈论题真的是五花八门,从较为基础的\(Anti-Nim\)到中间混进来的一道水题,再到不知道有啥用的斐波那契博弈,以及一道怎么也想不到是博弈论的神奇贪心题,最后是这道玄学的二分图匹配,一波操作下来我真的是一脸懵逼。

看来我还是太弱了。。。

题意转化

首先我们要知道一个结论:一个格子不可能被经过多次。

为什么呢?因为如果你从一个格子出发,再重新回到起点,必然是在第偶数步。而操作的过程肯定是黑白相间的,因此第一步和第偶数步不可能是同一种颜色,也就不可能再次回到该点。

于是,我们可以把原先的操作改为移动空白格子,使其走过的路径黑白相间。

黑白相间,我们就需要想到二分图反正我是没想到),进而想到二分图匹配

必胜策略

考虑在怎样的情况下,当前的决策者有着必胜策略。

依旧先给出结论:若除去当前点后的最大匹配小于保留当前点时的最大匹配,则当前的决策者有着必胜策略。

为什么呢?

假设在除去当前点后仍存在一个最大匹配,那我们从当前点必然只能沿非匹配边(如果没有,就说明输了)走向另一端的一个点,而另一端的点必然能够通过一条匹配边(必然存在,否则就不是最大匹配了)走回来。

也就是说,从这边不一定能找到一条边过去,但从那边却一定能找到一条边回来,显然某一刻无法再过去,那么就输了。

反之,若除去当前点后不存在最大匹配了,按照类似的证明步骤,便可得当前决胜者存在必胜策略。

具体实现

注意,在一般的二分图匹配(这里主要指匈牙利算法)中,我们通常只考虑一边对于另一边的连边以及匹配关系。

但在这道题中,由于要除去一些点,还要在较低复杂度内求出除去这些点后的最大匹配,因此我们需要双向连边,并记录双向的匹配关系。

在具体实现时,要求除去当前点后的最大匹配,其实只要给当前点打个删除标记,然后看原先与它匹配的点(若原先就没有与它匹配的点,显然删去它不影响最大匹配)能否找到新的点匹配,若找不到说明除去当前点后的最大匹配小于保留该点时的最大匹配,存在答案。

所以这道题代码实现其实还是比较简洁清晰的。

代码

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 40
#define K 1000 
#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)
using namespace std;
int n,m,k,t0,t1,f[2*K+5],a[N+5][N+5],p[N+5][N+5];char st[N+5];
namespace Hungarian//匈牙利算法
{
	int ee,lnk[N*N+5];struct edge {int to,nxt;}e[4*N*N+5];
	int ti,s[N*N+5],vis[N*N+5],del[N*N+5];
	I bool Match(CI x)//匹配
	{
		if(del[x]) return 0;for(RI i=lnk[x];i;i=e[i].nxt)
		{
			if(vis[e[i].to]==ti||del[e[i].to]) continue;vis[e[i].to]=ti;//若访问过,或已删去,不再访问
			if(!s[e[i].to]||Match(s[e[i].to])) return s[s[e[i].to]=x]=e[i].to;//注意记下双向匹配关系
		}return 0;
	}
	I void Build() {for(RI i=1;i<=t1;++i) ++ti,Match(i);}//初始化
}using namespace Hungarian;
int main()
{
	RI i,j,x,y,u,v;scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i) for(scanf("%s",st+1),j=1;j<=m;++j) switch(st[j])
	{
		case 'X':a[i][j]=1,p[i][j]=++t1;break;
		case 'O':a[i][j]=0,p[i][j]=++t0;break;
		case '.':a[i][j]=1,p[u=i][v=j]=++t1;break;//由于第一步是走到白格子,故把空白格视作黑格子
	}
	for(i=1;i<=n;++i) for(j=1;j<=m;++j) !a[i][j]&&(p[i][j]+=t1);//与一般二分图匹配不同,两端点要有不同编号
	for(i=1;i<=n;++i) for(j=1;j<=m;++j)//枚举格子连边
		i^n&&a[i][j]^a[i+1][j]&&(add(p[i][j],p[i+1][j]),add(p[i+1][j],p[i][j])),//向下
		j^m&&a[i][j]^a[i][j+1]&&(add(p[i][j],p[i][j+1]),add(p[i][j+1],p[i][j]));//向右
	for(Build(),scanf("%d",&k),k<<=1,i=0;i<=k;scanf("%d%d",&u,&v),++i)//枚举操作
		del[x=p[u][v]]=1,(y=s[x])&&(s[x]=s[y]=0,++ti,!Match(y))&&(f[i]=1);//给匹配的点找新的匹配
	RI cnt=0;for(k>>=1,i=1;i<=k;++i) f[2*i-2]&&f[2*i-1]&&++cnt;printf("%d\n",cnt);//统计答案个数
	for(i=1;i<=k;++i) f[2*i-2]&&f[2*i-1]&&printf("%d\n",i);return 0;//输出答案
}
上一篇:NOI2011 Noi嘉年华(神级dp)


下一篇:js算法-242有效的字母异位词