POJ 1358 Housing Complexes(二分整合)

タイトルリンク:http://poj.org/problem?id=1358
标题:K個のn*mの空き地を与え、アルファベットA-Zは障害を表す.各ブロックについて、あるアルファベットを全部持って行って、h*wの空き地が現れます.しかし、それぞれのアルファベットが1つのブロックの中で別のブロックに取られると、このようなアルファベットを持つことは許されません.Kブロックの中で最大でどれだけのh*wの空き地が現れることができることを求めますか?
構想:(1)まず,各ブロックにどのアルファベットを持ち出すとh*wの空き地が現れるかを計算する.f[n][m][26]、f[i][j][k]は[1,1]から[i,j]までの矩形内kが出現した回数を表し、その後、区間減算を用いて任意のh*wの領域内の各アルファベットが出現したか否かを求めることができる.h*wの領域にアルファベットが1つも現れていない場合は、このブロックは任意のアルファベットを消費する必要はありません.一つだけ現れたら、このアルファベットを持って行ってから題意を満たすことができます.(2)アルファベットと対応するKブロックで二分図を作成し,最大マッチングを求める.
 

int n,m,h,w,K,f[N][N][26];





struct node

{

    char s[N][N];

    int a[26],flag;





    void get()

    {

        int i;

        FOR1(i,n) RD(s[i]+1);

    }





    void init()

    {

        clr(a,0); flag=0; clr(f,0);

        int i,j,k,t,cnt;

        FOR1(i,n) FOR1(j,m)

        {

            FOR0(k,26)

            {

                f[i][j][k]=f[i-1][j][k]+f[i][j-1][k]-f[i-1][j-1][k];

            }

            if(s[i][j]!='0') f[i][j][s[i][j]-'A']++;

            if(i>=h&&j>=w)

            {

                cnt=0;

                FOR0(k,26) if(f[i][j][k]-f[i-h][j][k]-f[i][j-w][k]+f[i-h][j-w][k]) cnt++,t=k;

                if(!cnt)

                {

                    flag=1;

                    return;

                }

                else if(cnt==1) a[t]=1;

            }

        }

    }

};



node a[N];



int g[N][N],visit[N],match[N];



int DFS(int u)

{

    int i,v;

    FOR1(i,K) if(!visit[i]&&g[u][i])

    {

        visit[i]=1;

        if(match[i]==-1||DFS(match[i]))

        {

            match[i]=u;

            return 1;

        }

    }

    return 0;

}





int main()

{

    rush()

    {

        RD(K,n,m); RD(h,w);

        int i,j;

        FOR1(i,K) a[i].get(),a[i].init();

        int ans=0;

        clr(g,0);

        FOR1(i,K)

        {

            if(a[i].flag) ans++;

            else

            {

                FOR0(j,26) if(a[i].a[j]) g[j][i]=1;

            }

        }

        clr(match,-1);

        FOR0(i,26)

        {

            clr(visit,0);

            if(DFS(i)) ans++;

        }

        PR(ans);

    }

    return 0;

}