poj2195

题解：

简单KM

把每一个男的和房子分离

代码:

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

using namespace std;

const int NN=,MM=;

int a[NN][NN],v[NN][NN],g[NN][NN],lk[MM],lx[MM],ly[MM];

int visx[MM],visy[MM],slack[MM],N,M,n,n1,n2,cnt,ans;

int dfs(int x)

{

    visx[x]=cnt;

    for (int y=;y<=n;y++)

     {

        if (visy[y]==cnt) continue;

        int t=lx[x]+ly[y]-g[x][y];

        if (!t)

         {

             visy[y]=cnt;

            if (!lk[y]||dfs(lk[y])){lk[y]=x;return ;}

         }

        else if (slack[y]>t) slack[y]=t;

     }

    return ;

}

void KM()

{

    memset(lk,,sizeof(lk));

    memset(lx,,sizeof(lx));

    memset(ly,,sizeof(ly));

    for (int i=;i<=n;i++)

     for (int j=;j<=n;j++)lx[i]=max(lx[i],g[i][j]);

    for (int x=;x<=n;++x)

     {

        for (int i=;i<=n;i++)slack[i]=1e9;

        while (cnt++,!dfs(x))

         {

            int d=1e9;

            for (int i=;i<=n;i++)

             if (visy[i]!=cnt) d=min(d,slack[i]);

            for (int i=;i<=n;i++)

             {

                if (visx[i]==cnt) lx[i]-=d;

                if (visy[i]==cnt) ly[i]+=d;

                else slack[i]-=d;

             }

          }

     }

    return;

}

void work()

{

    n1=n2=ans=;

    for (int i=;i<=N;i++)

     for (int j=;j<=M;j++)

      {

        for (a[i][j]=getchar();a[i][j]!='.'&&a[i][j]!='m'&&a[i][j]!='H';a[i][j]=getchar());

        if (a[i][j]=='m') v[i][j]=++n1;

        if (a[i][j]=='H') v[i][j]=++n2;

     }

    for (int i=;i<=N;i++)

     for (int j=;j<=M;++j)

      {

        if (a[i][j]!='m') continue;

        for (int p=;p<=N;p++)

         for (int q=;q<=M;q++)

            if (a[p][q]=='H') g[v[i][j]][v[p][q]]=-abs(i-p)-abs(j-q);

      }

    n=n1;

    KM();

    for (int i=;i<=n;i++)ans+=lx[i]+ly[i];

    printf("%d\n",-ans);

    return;

}

int main()

{

    while (~scanf("%d%d",&N,&M)&&N|M) work();

    return ;

}