【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;
}