题解 P2825 【[HEOI2016/TJOI2016]游戏】

· · 题解

[HEOI2016/TJOI2016]游戏

匈牙利算法

可以先用这道题来热热手，熟悉匈牙利算法 P1129 [ZJOI2007]矩阵游戏

很容易发现若是没有软石头也没有硬石头，那么就是将所有的行标号i和列标号j连上边，再跑匈牙利算法。

也很好处理，就是软石头所在的坐标(x,y) ，x到y不连边。

因为硬石头的左右上下都不是相互影响的，所以，很容易的，它就多出来两个匹配点

不能理解？

这样的，之前只有软石头时，因为每一行只能放一个，每一列也只能放一个，所以，我们可以将每行看做匈牙利算法中的boy，将每列看做匈牙利算法中的girl，然后用boy去匹配girl，看最多能成几对,这样能保证每行最多只有一个，每列最多也只有一个

然后现在若有一个硬石头挡在中间，那么显然，原来相互影响的上下 现在不会了，原来放了左，就不能放右，而现在放了左还能放右

     上

  左  #  右

     下

所以，我们不妨将原来的一列（原上下为一列）分为两列（上一列，下一列），将原来的一行（原左右为一行）分为两行（左为一行，右为一行）

再拿样例模拟一下吧

行是这样变的

由

#111
2#22
33#3
xxx#

变为

#111
2#33
44#5
xxx#

列是这样的

由

#234
1#34
12#4
xxx#

变为

#245
1#45
13#5
xxx#

具体细节以及处理方法见代码：

#include<bits/stdc++.h>
using namespace std;
int hen[52][52],zong[52][52],c[2502];
int b[52][52],num,head[2502],cnt1=1,cnt2=1;
bool f[2502][2502],vis[2502],flag;
struct{
    int to,ne;
}a[2502];
void lian(int from,int to){
    num++;
    a[num].to=to;
    a[num].ne=head[from];
    head[from]=num;
}
int dfs(int x){
    int i;
    for(i=head[x];i;i=a[i].ne){
        if(!vis[a[i].to]){
            vis[a[i].to]=1;
            if(dfs(c[a[i].to])||!c[a[i].to]){               
                c[a[i].to]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    int n,m,i,j,ans=0;
    char c;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++){
            cin>>c;
            if(c=='#')b[i][j]=1;
            else if(c=='*')b[i][j]=2;
            else if(c=='x')b[i][j]=3;
        }
    cnt1=1;
    for(i=1;i<=n;i++){
        if(flag)cnt1++;flag=0;//flag=1表示这个标号已经用过了，若没用过当然没有换的必要，下面flag=1的判断同理
        for(j=1;j<=m;j++){
            if(b[i][j]==1&&flag)cnt1++;
            if(b[i][j]==2)hen[i][j]=cnt1,flag=1;
        }
    }//行的标号
    cnt2=1;flag=0;
    for(i=1;i<=m;i++){
        if(flag)cnt2++;flag=0;
        for(j=1;j<=n;j++){
            if(b[j][i]==1&&flag)cnt2++;
            if(b[j][i]==2)zong[j][i]=cnt2,flag=1;
        }
    }//列的标号
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(b[i][j]==2&&!f[hen[i][j]][zong[i][j]]){
                f[hen[i][j]][zong[i][j]]=1;
                lian(hen[i][j],zong[i][j]);
            }
    for(i=1;i<=cnt1;i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i))ans++;
    }
    cout<<ans<<endl;
    return 0;
}