【二分図マッチング】zoj 1654 Place the Robots

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1654
与えられたn*m(n，m<=50)の地図には、空き地、草地、壁があります。ロボットを空き地に置いて、衝突しないようにします。二つのロボットが同じ行または同じ列にいて、壁がないと、その二人は衝突します。ロボットはどれぐらい入れられますか？
この問題はzoj 1002と似ていますが、芝生が多いだけです。各行の連結ブロックの縮小点にx集合を入れ、各列の連結ブロックの縮小点にy集合を入れる。もし連結ブロックの間に交点があり、交点が空地であれば、その辺を結ぶ。その後に最大マッチングをすると解決できます。
この問題は他のモデルのことを考えやすいですが、このモデルは問題を解くのにあまり役に立たないです。空き地を頂点に、衝突の空き地が連なり、図の最大独立サブセットを探す。これはNPの問題です。今はいい解決方法がありません。
この二つのモデルはどうしてこんなに大きな違いがありますか？最初のモデルは空き地を端にしています。二つ目のモデルは空き地を点としています。したがって、図のモデリングは要素の選択に重要であることが分かる。
個人的には、このような連結ブロックのエッジの問題は、隣接表ではうまく処理されず、重辺が存在し、隣接表の効率が低下すると考えています。

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 2505
using namespace std;

int n ,m ,cntx ,cnty ,tmp[55][55] ,cx[MAXN] ,cy[MAXN] ;
char map[55][55] ;
bool vis[MAXN] ,flag[MAXN][MAXN] ;

void build()
{
    memset(flag,0,sizeof flag);
    memset(tmp,0,sizeof tmp);
    cntx=1;
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<m;++j)
            if(map[i][j]=='#')++cntx;
            else tmp[i][j]=cntx;
        if(map[i][m-1]!='#')++cntx;
    }

    cnty=1;
    for(int j=0;j<m;++j)
    {
        for(int i=0;i<n;++i)
            if(map[i][j]=='#')++cnty;
            else if(map[i][j]=='o')
                flag[tmp[i][j]][cnty]=1;
        if(map[n-1][j]!='#')++cnty;
    }
}

bool dfs(int u)
{
    for(int v=1;v<=cnty;++v)
        if(!vis[v]&&flag[u][v])
        {
            vis[v]=1;
            if(!cy[v]||dfs(cy[v]))
            {
                cx[u]=v ,cy[v]=u ;
                return 1;
            }
        }
    return 0;
}

int solve()
{
    memset(cx,0,sizeof cx);
    memset(cy,0,sizeof cy);
    int ans=0;
    for(int i=1;i<=cntx;++i)
        if(!cx[i])
        {
            memset(vis,0,sizeof vis);
            ans+=dfs(i);
        }
    return ans;
}

int main()
{
    int T ;
    scanf("%d",&T );
    for(int cas=1;cas<=T;++cas)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;++i)
            scanf("%s",map[i]);
        build();
        printf("Case :%d
%d
",cas,solve());
    }
    return 0;
}