BZOJ 1443 JSOI2009 游戲Game 二分圖博弈

BZOJ 1443 JSOI2009 游戲Game 二分圖博弈

題目大意：給定一個矩陣，一些位置有障礙，先手放置在某個位置，後手移動，先手再移動，一個格子只能經過一次，問是否先手必勝

二分圖博弈= = 將矩陣建成二分圖，考慮二分圖博弈的模型：

給定一個二分圖，每個點只能走一次，先手選定位置後手走，問是否先手必勝

那麼對於任意一個點，如果存在一個最大匹配中這個點沒有被匹配，那麼先手從這個點開始存在必勝策略

先手放置後，後手無論走到哪個點，先手一定能沿著匹配邊走回去

如果不存在匹配邊，說明找到了一條增廣路，與最大匹配的前提相悖，故一定存在匹配邊

當二分圖存在完備匹配時先手必敗。

這個題還讓我們求出先手選擇哪些點可以必勝

那麼我們做兩次最大匹配，每次只考慮左邊的點哪些可以必勝

枚舉每個未匹配的點，沿著出邊->匹配邊->出邊->匹配邊的順序開始深搜，深搜到的所有左側的點就是左側的可選點集。

時間復雜度O(n^2) 雖然數據范圍是10000但是匈牙利算法的常數很小 親測可過

坑比樣例- - 別忘了輸出WIN。。。

#include 
#include 
#include 
#include 
using namespace std;
struct abcd{
	int to,next;
}table[20200];
int head[5050],tot;
int m,n,n1,n2;
char map[110][110];
int pos[110][110];
bool ans[2][5050];
void Add(int x,int y)
{
	table[++tot].to=y;
	table[tot].next=head[x];
	head[x]=tot;
}
namespace Bipartite_Graph_Maximum_Match{
	int result[5050];
	bool state[5050],lonely[5050];
	bool Hungary(int x)
	{
		int i;
		for(i=head[x];i;i=table[i].next)
		{
			if(state[table[i].to])
				continue;
			state[table[i].to]=1;
			if( !result[table[i].to] || Hungary(result[table[i].to]) )
			{
				result[table[i].to]=x;
				return true;
			}
		}
		return false;
	}
	void DFS(int x,bool ans[])
	{
		int i;
		ans[x]=true;
		for(i=head[x];i;i=table[i].next)
			if(!ans[result[table[i].to]])
				DFS(result[table[i].to],ans);
	}
}
using namespace Bipartite_Graph_Maximum_Match;
void Initialize()
{
	memset(head,0,sizeof head);
	tot=0;
	memset(result,0,sizeof result);
	memset(lonely,0,sizeof lonely);
}
int main()
{

	static const int dx[]={0,0,1,-1};
	static const int dy[]={1,-1,0,0};
	int i,j,k;
	cin>>m>>n;
	for(i=1;i<=m;i++)
	{
		scanf("%s",map[i]+1);
		for(j=1;j<=n;j++)
			if(map[i][j]=='.')
				pos[i][j]=++(i+j&1?n1:n2);
	}

	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
			if( i+j&1 && map[i][j]=='.' )
				for(k=0;k<4;k++)
				{
					int x=i+dx[k];
					int y=j+dy[k];
					if(x<=0||y<=0||x>m||y>n||map[x][y]=='#')
						continue;
					Add(pos[i][j],pos[x][y]);
				}
	int matches=0;
	for(i=1;i<=n1;i++)
	{
		memset(state,0,sizeof state);
		if( Hungary(i) )
			matches++;
		else
			lonely[i]=true;
	}
	if( matches==n1 && matches==n2 )
		return cout<<"LOSE"<m||y>n||map[x][y]=='#')
						continue;
					Add(pos[i][j],pos[x][y]);
				}
	for(i=1;i<=n2;i++)
	{
		memset(state,0,sizeof state);
		if( !Hungary(i) )
			lonely[i]=1;
	}
	for(i=1;i<=n2;i++)
		if(lonely[i])
			DFS(i,ans[0]);

	cout<<"WIN"<