二分图增广路

千城_Dhmc · 2021-02-25 12:01:52 · 题解

吐槽：这道题看起来难做起来简（也）单（难）。

进入正题：

这个游戏是在一个 n 行 m 列的棋盘上进行的。游戏开始之前，棋盘上有一个格子是空的，其它的格子中都放置了一枚棋子，棋子或者是黑色，或者是白色。每一局游戏总是兔兔先操作，之后双方轮流操作，具体操作为：兔兔每次操作时，选择一枚与空格相邻的白色棋子，将它移进空格。蛋蛋每次操作时，选择一枚与空格相邻的黑色棋子，将它移进空格。第一个不能按照规则操作的人输掉游戏。

这道题很显然要用到深搜，我们先审清楚题意。A 一步走错的判定：A 走这步之前，A 选手采用最优策略必胜；A 走这步之后，B 选手采用最优策略必胜。

这道题和 AT 里的一道水题很像，那道题是谁先没糖吃谁输。

下面附上AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,cnt,tot,head[2500],match[2500],res[2010],win[2010];
char g[50][50]; 
bool vis[2500],block[2500],color[50][50];
int dx[4]={1,0,0,-1};
int dy[4]={0,1,-1,0};
struct node{//用结构体定义
    int to,nxt;
}; 
node edge[2500*2*4];
void addedge(int s,int e) {
    cnt++;
    edge[cnt].to=e;
    edge[cnt].nxt=head[s];
    head[s]=cnt;
    return;
}
bool dfs(int x){//深搜
    for(int i=head[x];i!=0;i=edge[i].nxt){
        int y=edge[i].to;
        if(block[y]==true){
            continue;
        }
        if(vis[y]==false){
            vis[y]=true;
            if(match[y]==0||dfs(match[y])==true) {
                match[y]=x; 
                match[x]=y; 
                return true;
            }
        }
    }
    return false;
}
int get_id(int x,int y){
    return (x-1)*m+y;
} 
bool check(int x,int y){
    if(x<1||x>n||y<1||y>m||color[x][y]==false){
        return false;
    }
    return true;    
}

int main(){
    cin>>n>>m;//输入
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>g[i][j]; //n行m列描述初始棋盘
        }
    }
    int sx,sy;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(g[i][j]=='O'){
                color[i][j]=true;
            }
            else if(g[i][j]=='.'){
                sx=i;
                sy=j;
            }
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(color[i][j]==true){
                continue;
            } 
            int cur=get_id(i,j); 
            for(int k=0;k<4;k++){
                int nx=i+dx[k];
                int ny=j+dy[k];
                if(check(nx,ny)==false){
                    continue;
                }
                int nxt=get_id(nx,ny);
                addedge(cur,nxt); 
                addedge(nxt,cur); 
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(color[i][j]==false){
                continue;
            }
            memset(vis,0,sizeof(vis));
            int cur=get_id(i,j); 
            if(dfs(cur)==true){
                ans++;
            } 

        }
    }
    int k; 
    cin>>k;
    for(int i=1;i<=2*k;i++){
        int cur=get_id(sx,sy);
        block[cur]=true; 
        if(match[cur]==0){
            win[i]=false;
        } 
        else{
            int nxt=match[cur];
            match[cur]=match[nxt]=0;  
            memset(vis,0,sizeof(vis));
            if(dfs(nxt)==true){
                win[i]=false;
            }else{
                win[i]=true; 
            }
        }
        cin>>sx>>sy;
    }

    for(int i=1;i<=k;i++){
        if(win[2*i-1]==true&&win[2*i]==true){
            res[++tot]=i; 
        }
    }
    cout<<tot<<endl;//犯错的总次数
    for(int i=1;i<=tot;i++){
        cout<<res[i]<<endl;//错误编号
    }
    return 0;
}
//请勿作弊，棕名警告

不喜勿喷。