首页 > 其他 > 详细

P2825 [HEOI2016/TJOI2016]游戏

时间:2019-09-15 17:10:40      阅读:72      评论:0      收藏:0      [点我收藏+]

P2825 [HEOI2016/TJOI2016]游戏

套路二分图

发现如果没有讨厌的两种墙,这道题就是一个经典的二分图模型,行列匹配

但是有两种墙

先看看样例

技术分享图片

我们以行为例子,导出可以一下子一起消掉的连通块

大致是这样

# 1 1 1

2 # 3 3

4 4 # 5

6 6 6 #

列一样

这样一个空地就匹配了两条链

二分图最大匹配一下即可

代码:

#include<bits/stdc++.h>
using namespace std;
#define re register
const int N=55,M=3005;
int n,m;
char s[N][N];
int cnt_x=0,cnt_y=0;
int be_x[N][N],be_y[N][N];
int c[M][M]={0};
int sx[M],sy[M],us[M];
int ans=0;
inline bool work(int u){
    for(re int v=1;v<=cnt_y;v++){
        if(c[u][v]&&!us[v]){
            us[v]=1;
            if(sy[v]==-1||work(sy[v])){
                sx[u]=v;
                sy[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    memset(sx,-1,sizeof(sx));
    memset(sy,-1,sizeof(sy));
    scanf("%d%d",&n,&m);
    for(re int i=1;i<=n;i++){
        for(re int j=1;j<=m;j++){
            char c;
            cin>>c;
            s[i][j]=c;
        }
    }
    for(re int i=1;i<=n;i++){
        for(re int j=1;j<=m;j++){
            if(s[i][j]==#) continue;
            if(j==1||s[i][j-1]==#){
                cnt_x++;
                be_x[i][j]=cnt_x;
            }
            else be_x[i][j]=be_x[i][j-1];
        }
    }
    /*
    for(re int i=1;i<=n;i++){
        for(re int j=1;j<=m;j++){
            cout<<be_x[i][j]<<" ";
        }
        cout<<endl;
    }
    */
    for(re int j=1;j<=m;j++){
        for(re int i=1;i<=n;i++){
            if(s[i][j]==#) continue;
            if(i==1||s[i-1][j]==#){
                cnt_y++;
                be_y[i][j]=cnt_y;
            }
            else be_y[i][j]=be_y[i-1][j];
        }
    }
    /*
    for(re int i=1;i<=n;i++){
        for(re int j=1;j<=m;j++){
            cout<<be_y[i][j]<<" ";
        }
        cout<<endl;
    }
    */
    for(re int i=1;i<=n;i++){
        for(re int j=1;j<=m;j++){
            if(s[i][j]!=*) continue;
            c[be_x[i][j]][be_y[i][j]]=1;
        }
    }
    for(int i=1;i<=cnt_x;i++){
        memset(us,0,sizeof(us));
        ans+=work(i);
    }
    printf("%d\n",ans);
    return 0;
}

 

P2825 [HEOI2016/TJOI2016]游戏

原文:https://www.cnblogs.com/QYJ060604/p/11522973.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!