BZOJ 1443 JSOI 2009 游戲Game 二分圖+博弈

BZOJ 1443 JSOI 2009 游戲Game 二分圖+博弈

題目大意：給出一個帶有壞點的網格圖，每次移動棋子到相鄰的格子中，要求格子不能重復，問先手是否有必勝策略，如果有，輸出所有的棋子可以擺放的初值位置。

思路：很經典的二分圖博弈模型，將圖黑白染色，就變成了二分圖。求最大匹配之後，如果是在二分匹配上的邊，每次先手從左側走到右側，後手就一定能從右邊走回來，這樣就是先手輸了。具體見：http://blog.sina.com.cn/s/blog_76f6777d0101inwe.html

建立網絡流模型，跑最大流，在殘量網絡上從S能夠搜到的左側的點和右側的能夠搜到T的點都是滿足要求的點。

CODE：

#define _CRT_SECURE_NO_WARNINGS

#include 
#include 
#include 
#include 
#include 
#define MAX 2100
#define MAXP 20100
#define MAXE 1000010
#define S 0
#define T (MAXP - 1)
#define INF 0x3f3f3f3f
using namespace std;
const int dx[] = {0,1,-1,0,0};
const int dy[] = {0,0,0,1,-1};

int ans[MAXP];
bool v[MAXP];

struct MaxFlow{
	int head[MAXP],total;
	int next[MAXE],aim[MAXE],flow[MAXE];

	int deep[MAXP];

	MaxFlow():total(1) {}
	void Add(int x,int y,int f) {
		next[++total] = head[x];
		aim[total] = y;
		flow[total] = f;
		head[x] = total;
	}
	void Insert(int x,int y,int f) {
		//cout << x << ' ' << y << ' ' << f << endl;
		Add(x,y,f);
		Add(y,x,0);
	}
	bool BFS() {
		static queue q;
		while(!q.empty())	q.pop();
		memset(deep,0,sizeof(deep));
		deep[S] = 1;
		q.push(S);
		while(!q.empty()) {
			int x = q.front(); q.pop();
			for(int i = head[x]; i; i = next[i])
				if(flow[i] && !deep[aim[i]]) {
					deep[aim[i]] = deep[x] + 1;
					q.push(aim[i]);
					if(aim[i] == T)	return true;
				}
		}
		return false;
	}
	int Dinic(int x,int f) {
		if(x == T)	return f;
		int temp = f;
		for(int i = head[x]; i; i = next[i])
			if(flow[i] && deep[aim[i]] == deep[x] + 1 && temp) {
				int away = Dinic(aim[i],min(flow[i],temp));
				if(!away)	deep[aim[i]] = 0;
				flow[i] -= away;
				flow[i^1] += away;
				temp -= away;
			}
		return f - temp;
	}
}solver;

int m,n;
char s[MAX][MAX];
int num[MAX][MAX];
bool col[MAXP];

bool t[MAXP];

void DFS(int x,int f)
{
	t[x] = true;
	if(col[x] == f && x != S && x != T)
		ans[++ans[0]] = x;
	for(int i = solver.head[x]; i; i = solver.next[i])
		if(solver.flow[i] == f && !t[solver.aim[i]])
			DFS(solver.aim[i],f);
}

void GetAns()
{
	DFS(S,1);
	memset(t,false,sizeof(t));
	DFS(T,0);
}

inline void OutPut(int x)
{
	printf("%d %d\n",(x - 1) / n + 1,(x - 1) % n + 1);
}

int main()
{
	cin >> m >> n;
	for(int i = 1; i <= m; ++i)
		scanf("%s",s[i] + 1);
	int cnt = 0;
	for(int i = 1; i <= m; ++i)
		for(int j = 1; j <= n; ++j)
			num[i][j] = ++cnt;
	for(int i = 1; i <= m; ++i)
		for(int j = 1; j <= n; ++j) {
			if(s[i][j] == '#')	continue;
			if(!((i + j)&1))
				solver.Insert(S,num[i][j],1),col[num[i][j]] = true;
			else {
				solver.Insert(num[i][j],T,1);
				continue;
			}
			for(int k = 1; k <= 4; ++k) {
				int fx = i + dx[k],fy = j + dy[k];
				if(!fx || !fy || fx > m || fy > n)	continue;
				if(s[fx][fy] == '.')
					solver.Insert(num[i][j],num[fx][fy],1);
			}
		}
	while(solver.BFS())
		solver.Dinic(S,INF);
	GetAns();
	if(!ans[0])	puts("LOSE");
	else {
		puts("WIN");
		sort(ans + 1,ans + ans[0] + 1);
		for(int i = 1; i <= ans[0]; ++i)
			OutPut(ans[i]);
	}
	return 0;
}