BZOJ 1443 JSOI 2009 游戏Game 二分图+博弈
题目大意:给出一个带有坏点的网格图,每次移动棋子到相邻的格子中,要求格子不能重复,问先手是否有必胜策略,如果有,输出所有的棋子可以摆放的初值位置。
思路:很经典的二分图博弈模型,将图黑白染色,就变成了二分图。求最大匹配之后,如果是在二分匹配上的边,每次先手从左侧走到右侧,后手就一定能从右边走回来,这样就是先手输了。具体见:http://blog.sina.com.cn/s/blog_76f6777d0101inwe.html
建立网络流模型,跑最大流,在残量网络上从S能够搜到的左侧的点和右侧的能够搜到T的点都是满足要求的点。
CODE:
#define _CRT_SECURE_NO_WARNINGS #include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #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<int> 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; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。