「题解」「JSOI2009」游戏 game

一个神奇的网络流(二分图)+博弈论问题。

题目链接:Luogu P4055/BZOJ 1443

题目

题目简述

有一个棋盘,大小为 $n\times m$,有些格子上有障碍,一个棋子应该被放在没有障碍的格子上面。

现在有一个游戏,一个人决定棋子初始位置,另一个人先手移动,然后不断移动,同一个格子不能被经过两次。当谁无法继续移动棋子,谁输。

数据范围

变量数据范围
$n$$1\leq n\leq 100$
$m$$1\leq m\leq 100$

时空限制

题目编号时间限制空间限制
Luogu P4055$1\text{s}$$125\text{MiB}$
BZOJ 1443$10\text{s}$$162\text{MiB}$

题解

思路

考虑这样一个问题。棋盘有阻挡,所以自然想到二分图匹配,对于先手而言,若二分图不存在完美匹配,则放在非匹配点一定是最优的。因为后手的第一步必定走到一个匹配点,先手只需要保证一直沿着匹配边走即可,因为不可能存在非匹配边、匹配边交叉出现的增广路,即先手总是能比后手多走一步(根据最大匹配的定义),若二分图存在完美匹配,那么先手无论如何放置都会输,具体同理,那么先判断是否是完美匹配,若是这道题也就完了,不是的话找到非匹配点就行了。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
typedef unsigned long long ull;
#define INF 0X3F3F3F3F
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=100+5;
const int MAXM=100+5;
const int MAXSIZE=MAXN*MAXM; //点数的数据范围

inline void Read(void);
inline void Work(void);

int main(void){
    Read();
    Work();
    return 0;
}

int n,m,s,t;
char M[MAXN][MAXM];
int cnt=1,head[MAXSIZE],to[MAXSIZE*8],w[MAXSIZE*8],Next[MAXSIZE*8];

inline void Add_Edge(reg int u,reg int v,reg int len){
    Next[++cnt]=head[u];
    to[cnt]=v;
    w[cnt]=len;
    head[u]=cnt;
    return;
}

inline void Add_Tube(reg int u,reg int v,reg int len){
    Add_Edge(u,v,len);
    Add_Edge(v,u,0);
    return;
}

inline void Read(void){
    n=read(),m=read(),s=0,t=n*m+1; //注意源点和汇点
    for(reg int i=1;i<=n;++i)
        scanf("%s",M[i]+1); //读入棋盘
    return;
}

int dep[MAXSIZE];
queue<int> Q;

inline bool BFS(int s,reg int t){
    memset(dep,-1,sizeof(dep)); //初始化 dep[]
    while(!Q.empty())Q.pop(); //清空队列
    dep[s]=1,Q.push(s); //初始化起点
    while(!Q.empty()){ //开始建设分层图
        reg int ID=Q.front();
        Q.pop();
        for(reg int i=head[ID];i;i=Next[i])
            if(dep[to[i]]==-1&&w[i]>0){ //更新深度
                dep[to[i]]=dep[ID]+1;
                Q.push(to[i]);
            }
    }
    return dep[t]!=-1; //汇点是否可达
}

int cur[MAXSIZE]; //cur[] 用于 Dinic 的当前弧优化

inline int DFS(reg int ID,reg int t,reg int lim){
    if(ID==t)
        return lim;
    reg int flow=0;
    for(reg int &i=cur[ID];i;i=Next[i])
        if(dep[to[i]]==dep[ID]+1&&w[i]>0){
            reg int f=DFS(to[i],t,min(lim-flow,w[i]));
            if(f){
                flow+=f; //求和
                w[i]-=f;
                w[i^1]+=f; //反向边
                if(flow==lim)
                    break; //如果满流就退出
            }
        }
    return flow;
}

inline int Dinic(reg int s,reg int t){
    reg int res=0;
    while(BFS(s,t)){
        memcpy(cur,head,sizeof(head)); //复制表头
        res+=DFS(s,t,INF);
    }
    return res;
}

inline int GetID(reg int i,reg int j){
    return (i-1)*m+j;
}

bool flag; //flag 表示是否存在答案
bool bel[MAXSIZE];
bool vis[MAXSIZE];
bool ans[MAXSIZE]; //ans[i] 表示点 i 是否是答案

inline void GetAns(reg int ID,reg bool lim){
    if(vis[ID])
        return;
    vis[ID]=true;
    if(bel[ID]==lim){
        ans[ID]=true;
        flag=true;
    }
    for(reg int i=head[ID];i;i=Next[i])
        if((bool)w[i]==lim)
            GetAns(to[i],lim);
    return;
}

inline void Work(void){
    const int dx[]={-1,0,0,1};
    const int dy[]={0,-1,1,0};
    for(reg int i=1;i<=n;++i)
        for(reg int j=1;j<=m;++j){
            reg int now=GetID(i,j);
            if(((i^j)&1)&&M[i][j]!='#'){
                bel[now]=true;
                Add_Tube(s,now,1);
                for(reg int k=0;k<4;++k){
                    reg int fx=i+dx[k],fy=j+dy[k];
                    if(1<=fx&&fx<=n&&1<=fy&&fy<=m&&M[fx][fy]!='#')
                        Add_Tube(now,GetID(fx,fy),1);
                }
            }
            else if(!((i^j)&1)&&M[i][j]!='#')
                Add_Tube(now,t,1);
        }
    Dinic(s,t); //求最大流
    GetAns(s,1); //求跟源点相连的答案
    memset(vis,false,sizeof(vis));
    GetAns(t,0); //求跟汇点相连的答案
    if(flag){ //存在答案
        puts("WIN");
        for(reg int i=1;i<=n;++i)
            for(reg int j=1;j<=m;++j)
                if(ans[GetID(i,j)])
                    printf("%d %d\n",i,j); //输出答案
    }
    else
        puts("LOSE");
    return;
}