bzoj 2437[Noi2011]兔兔与蛋蛋黑白染色二分图+博弈+匈牙利新姿势

noi2011 兔兔与蛋蛋

题目大意

直接看原题吧

就是\(n*m\)的格子上有一些白棋和一些黑棋和唯一一个空格

兔兔先手，蛋蛋后手

兔兔要把与空格相邻的其中一个白棋移到空格里

蛋蛋要把与空格相邻的其中一个黑棋移到空格里

谁不能移动谁输

分析

这篇博客挺好的

我们可以将题意转化成兔兔将空格移到白棋那里

蛋蛋将空格移动到黑棋那里

转化成图黑白染色，变成二分图

我们设空格染成黑色

那空格移动的轨迹一定是：

黑\(~\)-白-黑-白-黑

对应的是：

空格-白棋-黑棋-白棋-黑棋

所以染成白色且为白棋\(~\)或\(~\)染成黑色且为黑棋

的才是合法点（其他点不可能移动的）

将相邻合法点连边

同时把空格当成黑棋看

又根据奇偶性，从空格从一个点出发不可能绕回那个点

博弈

假如我们现在求出了一个最大匹配

那么如果一个点一定在最大匹配中，那么他有必胜策略

否则没有

证明：

已匹配的边记为\(A\)

未匹配的边记为\(B\)

那么从一个点出发走到无路可走\(~~\)且\(~~\)有A尽量走A有以下几种情况：（图自行脑补）

根据匹配，不可能出现\(AA\)

思考一下，不可能出现\(BB\)（因为前一个\(B\)没有匹配边\(A\)了,后一个\(B\)无路可走了）

还有就是从一个点出发有\(B\)则那个点出发还一定有个\(A\)

1.\(ABAB\)

这种情况\(AB\)可以互换，最大匹配不变

出发点不一定在最大匹配中，先手走\(A\)会让对方有必胜策略

2.\(BABA\)

同上

出发点不一定在最大匹配中，先手走\(B\)会让对方有必胜策略

3.\(BABAB\)

因为从一个点出发有\(B\)则那个点出发还一定有个\(A\)

交换\(AB\)最大匹配不变，且出发点依然在最大匹配中

出发点一定在最大匹配中，先手走\(B\)或\(A\)都能赢

4.\(ABABA\)

这种情况出发点一定在最大匹配中，先手走\(A\)就赢了

做法

证明完了

现在如何判断一个点是否一定在最大匹配中呢？

首先如果本来就不在最大匹配直接就不行了

否则删掉这个点，并断掉这个点的匹配边，从它匹配点增广

匹配点能增广它就不一定在最大匹配了

做法

于是我们动态ban点

每读入一个操作就ban掉一个点就好了

姿势

匈牙利vis数组可以用时间戳

标号都不一样的话可以两边一起匹配

bool xyl(int x){

	int p,y;

	for(p=g[x];p;p=e[p].nxt)

	if(vis[y=e[p].y]!=T&&!del[y]){

		vis[y]=T;

		if(lnk[y]==-1||xyl(lnk[y])){

			lnk[y]=x;//

			lnk[x]=y;//

			return 1;

		}

	}

	return 0;

}

int main(){

	for(i=1;i<=cnt;i++)

		if(lnk[i]==-1){

			T++;

			xyl(i);

	}

}

solution

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cmath>

#include <algorithm>

using namespace std;

const int M=1603;

const int N=43;

inline int rd(){

	int x=0;bool f=1;char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

	for(;isdigit(c);c=getchar()) x=x*10+c-48;

	return f?x:-x;

}

int n,m,nm,K,T;

int g[M],te;

struct edge{int y,nxt;}e[M<<3];

char s[N][N];

int num[N][N],cnt,ck;

bool win[2007];

int del[M];

int lnk[M];

int vis[M];

void addedge(int x,int y){

	e[++te].y=y;e[te].nxt=g[x];g[x]=te;

}

bool xyl(int x){

	int p,y;

	for(p=g[x];p;p=e[p].nxt)

	if(vis[y=e[p].y]!=T&&!del[y]){

		vis[y]=T;

		if(lnk[y]==-1||xyl(lnk[y])){

			lnk[y]=x;

			lnk[x]=y;

			return 1;

		}

	}

	return 0;

}

int main(){

	int i,j,x,y,nw;

	n=rd(),m=rd();

	for(i=1;i<=n;i++) scanf("%s",s[i]+1);

	for(i=1;i<=n;i++)

	for(j=1;j<=m;j++)

		if(s[i][j]=='.'){

			s[i][j]='X';//要使它有连边

			x=i; y=j;//x，y存的是空格位置

			ck=(i+j)%2;

			break;

		}

	for(i=1;i<=n;i++)

	for(j=1;j<=m;j++){

		if(s[i][j]=='X'&&(i+j)%2==ck) num[i][j]=++cnt;

		if(s[i][j]=='O'&&(i+j)%2!=ck) num[i][j]=++cnt;

	}

	for(i=1;i<=n;i++)

	for(j=1;j<=m;j++)

	if(num[i][j]){

		if(i>1&&num[i-1][j]) addedge(num[i][j],num[i-1][j]);

		if(i<n&&num[i+1][j]) addedge(num[i][j],num[i+1][j]);

		if(j>1&&num[i][j-1]) addedge(num[i][j],num[i][j-1]);

		if(j<m&&num[i][j+1]) addedge(num[i][j],num[i][j+1]);

	}

	memset(lnk,-1,sizeof(lnk));

	for(i=1;i<=cnt;i++)

	if(lnk[i]==-1){

		T++;

		xyl(i);

	}

	K=rd();

	for(i=1;i<=K*2;i++){

		nw=num[x][y];

		del[nw]=1;

		if(lnk[nw]==-1) win[i]=0;

		else{

			int tp=lnk[nw];

			lnk[nw]=lnk[tp]=-1;

			T++;

			win[i]= !xyl(tp);

		}

		x=rd(),y=rd();

	}

	int ans=0;

	for(i=1;i<=K;i++)

	if(win[i*2]&&win[i*2-1]) ans++;

	printf("%d\n",ans);

	for(i=1;i<=K;i++)

	if(win[i*2]&&win[i*2-1]) printf("%d\n",i);

	return 0;

}

bzoj 2437[Noi2011]兔兔与蛋蛋黑白染色二分图+博弈+匈牙利新姿势

题目大意

分析

博弈

做法

做法

姿势

solution