[JSOI2009]游戏Game
Time Limit:10000MS Memory Limit:165536K
Total Submit:21 Accepted:12
Case Time Limit:1000MS
Description
Input
输入数据首先输入两个整数N,M，表示了迷宫的边长。
接下来N行，每行M个字符，描述了迷宫。
Output
若小AA能够赢得游戏，则输出一行"WIN"，然后输出所有可以赢得游戏的起始位置，按行优先顺序输出
每行一个,否则输出一行"LOSE"（不包含引号）。
Sample Input
3 3
.##
…
#.#
Sample Output
2 3
3 2
Hint
对于100%的数据，有1≤n,m≤100。
对于30%的数据，有1≤n,m≤5。
Source
JSOI2009Day2
这题好那个啥囧。。。2个月前见到此题毫无思路。。。
然后上个星期突然有一点思路了。。
然后又考虑了N久。。。
（其实是看到了一道数学题，就是（2n+1）*(2n+1)的正方形上求证放的人有必胜策略，这个题目随便放在一个点上，然后吧其它的点按多米诺骨牌配对，然后每次别人走到一个点上我就到配对的那个点上。。。肯定赢。。。）
然后接着想。。那么这个是不是也跟最大匹配有关系呢。。。
想了很久秃然明白了囧。。。
如果一个点一定在最大匹配里。。。
所以从这点出发的交替路肯定只能到达匹配中的点。。
那么每次我都肯定可以顺着匹配边走。。。别人就被我搞死了。。。
如果一个点可以不在最大匹配里。。
那么在那个图里面。。。对方每次顺着匹配边走。。我就被搞死了。。。
所以只需要知道每个点是否可以不在最大匹配里。。。
一开始我直接暴力。。TLE。。
后来发现可以不在的点其实就是当前从vs可达的之类的。。。
就可以A了。。速度爆慢囧。。
Code：
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define tr(e,x) for(vector<int>::iterator e=x.begin();e!=x.end();e++)
#define All(x) x.begin(),x.end()
#define pb push_back
#define OK puts("OK")
const int inf=~0U>>1,maxn=100,maxv=maxn*maxn+10;
using namespace std;
struct Edge
{
int t,c;
Edge*next,*op;
Edge(int _t,int _c,Edge*_n):
t(_t),c(_c),next(_n){}
}*E[maxv]={};
void AddEdge(int s,int t,int c)
{
E[s]=new Edge(t,c,E[s]);
E[t]=new Edge(s,0,E[t]);
E[s]->op=E[t];E[t]->op=E[s];
}
int n,m,v,vs,vt;
bool M[maxn][maxn];
void BuildGraph()
{
v=n*m;vs=v++;vt=v++;
rep(i,n)rep(j,m)
if(M[i][j])
if((i+j)&1)
{
#define A(i,j) ((i)*m+(j))
#define build(ii,jj)
if(M[ii][jj])
AddEdge(A(i,j),A(ii,jj),1)
AddEdge(vs,A(i,j),1);
if(i)build(i-1,j);
if(j)build(i,j-1);
if(i+1<n)build(i+1,j);
if(j+1<m)build(i,j+1);
#undef build
}
else
{
AddEdge(A(i,j),vt,1);
#undef A
}
}
int Vis[maxv]={},flag=0;
int dfs(int x,int m)
{
if(x==vt)return m;
Vis[x]=flag;
for(Edge*e=E[x];e;e=e->next)if(e->c&&Vis[e->t]!=flag)
{
int d=dfs(e->t,min(m,e->c));
if(d) return e->c-=d,e->op->c+=d,d;
}
return 0;
}
void Init()
{
scanf("%d%d",&n,&m);char c;
rep(i,n)
{
scanf(" ");
rep(j,m)
c=getchar(),M[i][j]=c==’.’;
}
}
bool dead[maxv]={},type;
bool Type(int v)
{
return (v%m+v/m)&1;
}
int C;
void dfs(int x)
{
Vis[x]=flag;
if(Type(x)==type)
dead[x]=true;
for(Edge*e=E[x];e;e=e->next)
if(e->c==type&&Vis[e->t]!=flag)
dfs(e->t);
}
void Solve()
{
++flag;int Max=0;
while(int d=dfs(vs,inf))++flag,Max+=d;
++flag;
type=1;
dfs(vs);dead[vs]=false;
++flag;
type=0;
dfs(vt);dead[vt]=false;
bool has=false;
rep(i,v)if(dead[i]){has=true;break;}
if(has)
{
puts("WIN");
rep(i,v)if(dead[i])
{
int x=i/m,y=i%m;
printf("%d %dn",x+1,y+1);
}
}
else
{
puts("LOSE");
}
}
int main()
{
//freopen("in","r",stdin);
Init();
BuildGraph();
Solve();
}