【BZOJ1443】【JSOI2009】游戏Game 二分图+博弈

#include <stdio.h>
int main()
{
	puts("转载请注明出处谢谢");
	puts("http://blog.csdn.net/vmurder/article/details/43311795");
}


题解:二分图博弈经典模型模板题。


首先黑白染色。

然后我们考虑到有一种优秀的走法,

    就是先求个最大匹配,然后如果先手选择了一个最大匹配中的点,那么显然后手可以依照此点的匹配再走一步,然后先手无法走此匹配,就乱走一气,于是有两种情况:

一、又选了一个最大匹配中的点,显然回到了情况一。

二、他选了一个不在最大匹配中的点(显然是有这种情况的),如下图,先手走3,后手走2,先手走1赢了。

技术分享

于是,诶?先手赢了,靠啊,我考虑错了。


那么换一种方式考虑。

就是先手先选一个不在最大匹配里面的点,然后对手有两种情况:

一、走一个在最大匹配里的点,然后有了上面考虑错的那种情况,但是不同的是,如果出现了后手最后走某边达到一个非最大匹配中点,就代表出现了一条增广路,显然因为是最大匹配,所以这种情况是不会出现的,所以这种情况先手必胜。

二、走一个不在最大匹配里的点,然后?诶?这是显然的不对啊!直接增广了,连反向弧神马都不用!!!

于是~~~先手必胜。


但是如果所有的点都最大匹配了呢?(我整个人都最大匹配了)

    随便先手去选哪个点,后手都可以沿其匹配走,然后先手如果走,又是一个新的最大匹配中点,后手又走其匹配,然后后手就赢了。


胜负就是这种情况了~~~

然后是win时方案:

我们考虑到首先先手一定可以走一个非匹配点,显然这就赢了。

但是如果只输出这些点,显然样例都过不了!!!


我们拿上面那个图举例,就可以有两种选择。

这个怎么做呢?

我是拿网络流写的,这里就先介绍一种最大流时的做法吧:


我们dfs一遍,看从源点能到哪些染色时归到S集的点;

  再dfs一遍,看从哪些染色时归到T集的点能到汇点。

这些点就是答案!(注意建边时需要为有向边!就是反向弧初始流量为0!)


为什么呢?

首先非匹配点肯定是会被扫到的,

然后是匹配点中的可行点:

我们将如何扫到这些可行点呢?

以S集点为例,我们会先扫到一个可行点,然后扫到一个T集点,然后再通过已经有流量的反向弧回到一个匹配点,这样这个匹配点就是可行的了!

    原因:这显然是一个类似于增广路的过程,而最后的结果是我们用这个可行点代替了扫到的匹配点,并与那个T集点构成了匹配。、呃,不是很难理解吧?


代码:

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define P 200
#define N 101000
#define M 501000
#define inf 0x3f3f3f3f
using namespace std;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
struct KSD
{
	int v,len,next;
}e[M];
int head[N],cnt;
inline void add(int u,int v,int len)
{
	e[++cnt].v=v;
	e[cnt].len=len;
	e[cnt].next=head[u];
	head[u]=cnt;
}
inline void Add(int u,int v,int len){add(u,v,len),add(v,u,0);}
int s,t,d[N];
queue<int>q;
bool bfs()
{
	while(!q.empty())q.pop();
	memset(d,0,sizeof d);

	int i,u,v;
	q.push(s),d[s]=1;
	while(!q.empty())
	{
		u=q.front(),q.pop();
		for(i=head[u];i;i=e[i].next)
		{
			if(!d[v=e[i].v]&&e[i].len)
			{
				d[v]=d[u]+1;
				if(v==t)return 1;
				q.push(v);
			}
		}
	}
	return 0;
}
int dinic(int x,int flow)
{
	if(x==t)return flow;
	int remain=flow,i,v,k;
	for(i=head[x];i;i=e[i].next)
	{
		if(d[v=e[i].v]==d[x]+1&&e[i].len)
		{
			k=dinic(v,min(remain,e[i].len));
			if(!k)d[v]=0;
			e[i].len-=k,e[i^1].len+=k;
			remain-=k;
		}
	}
	return flow-remain;
}
char map[P][P];
int maxflow,n,m;
int id[P][P],idx[N],idy[N];
bool belong[N];
void build()
{
	int i,j,k;
	int x,y;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%s",map[i]+1);
		for(j=1;j<=m;j++)if(map[i][j]=='.')
		{
			id[i][j]=++cnt;
			idx[cnt]=i;
			idy[cnt]=j;
		}
	}
	s=cnt+1,t=cnt+2,cnt=1;
	for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(id[i][j])
	{
		maxflow++;
		if(i+j&1)
		{
			Add(s,id[i][j],1);
			belong[id[i][j]]=true;
			for(k=0;k<4;k++)
			{
				x=i+dx[k],y=j+dy[k];
				if(id[x][y])Add(id[i][j],id[x][y],1);
			}
		}
		else Add(id[i][j],t,1);
	}
}
bool vis[N];
int ans[N];
void dfs(int x,int d)
{
	int i,v;
	vis[x]=true;
	if(belong[x]==d)ans[++cnt]=x;
	for(i=head[x];i;i=e[i].next)
		if(e[i].len==d&&!vis[v=e[i].v])
			dfs(v,d);
}
int main()
{
	freopen("test.in","r",stdin);
	build();
	while(bfs())maxflow-=2*dinic(s,inf);
	if(!maxflow)
	{
		puts("LOSE");
		return 0;
	}
	else {
		puts("WIN");
		cnt=0;
		dfs(s,1);
		memset(vis,0,sizeof vis);
		dfs(t,0);
		sort(ans+1,ans+cnt+1);
		for(int i=1;i<=cnt;i++)if(ans[i]!=s&&ans[i]!=t)
			printf("%d %d\n",idx[ans[i]],idy[ans[i]]);
		return 0;
	}
	return 0;
}







郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。