POJ 2195

#include<iostream>//by Chengdacaizi

#include<stdio.h>

#include<vector>

#include<algorithm>

#include<math.h>

#define MAXN 105

#include <string>

#define inf 1000000000

#define _clr(x) memset(x,0xff,sizeof(int)*n)

using namespace std;

int _m[MAXN][MAXN];

vector<int> man;

vector<int> hou;

int match1[MAXN];

int match2[MAXN];

int kuhn_munkras(int m,int n,int mat[][MAXN],int* match1,int* match2);

int main()

{

    //freopen("acm.acm","r",stdin);

    int n;

    int m;

    int i;

    int j;

    char c;

    int tem1;

    int tem2;

    int temj1;

    int temj2;

    while(cin>>n>>m)

    {

        memset(_m,,sizeof(_m));

        if(!n&&!m)

            break;

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

        {

            for(j = ; j < m; ++ j)

            {

                cin>>c;

                if(c == 'm')

                    man.push_back(i*m+j);

                else if(c == 'H')

                    hou.push_back(i*m+j);

            }

        }

        for(i = ; i < man.size(); ++ i)

        {

            for(j = ; j < hou.size(); ++ j)

            {

                tem1 = man[i]/m;

                tem2 = man[i]%m;

                temj1 = hou[j]/m;

                temj2 = hou[j]%m;

                _m[i][j] = (-)*(abs(tem1 - temj1) + abs(tem2 - temj2));

            }

        }

        m = man.size();

        n = hou.size();

        if(m>n)

            iter_swap(&m,&n);

        cout<<-kuhn_munkras(m,n,_m,match1,match2)<<endl;

        man.clear();

        hou.clear();

    }

}

int kuhn_munkras(int m,int n,int mat[][MAXN],int* match1,int* match2){

    int s[MAXN],t[MAXN],l1[MAXN],l2[MAXN],p,q,ret=,i,j,k;//最佳匹配

    for (i=;i<m;i++)

        for (l1[i]=-inf,j=;j<n;j++)

            l1[i]=mat[i][j]>l1[i]?mat[i][j]:l1[i];

    for (i=;i<n;l2[i++]=);

    for (_clr(match1),_clr(match2),i=;i<m;i++){

        for (_clr(t),s[p=q=]=i;p<=q&&match1[i]<;p++)

            for (k=s[p],j=;j<n&&match1[i]<;j++)

                if (l1[k]+l2[j]==mat[k][j]&&t[j]<){

                    s[++q]=match2[j],t[j]=k;

                    if (s[q]<)

                        for (p=j;p>=;j=p)

                            match2[j]=k=t[j],p=match1[k],match1[k]=j;

                }

        if (match1[i]<){

            for (i--,p=inf,k=;k<=q;k++)

                for (j=;j<n;j++)

                    if (t[j]<&&l1[s[k]]+l2[j]-mat[s[k]][j]<p)

                        p=l1[s[k]]+l2[j]-mat[s[k]][j];

            for (j=;j<n;l2[j]+=t[j]<?:p,j++);

            for (k=;k<=q;l1[s[k++]]-=p);

        }

    }

    for (i=;i<m;i++)

        ret+=mat[i][match1[i]];

    return ret;

}
关注我的公众号，当然，如果你对Java, Scala, Python等技术经验，以及编程日记，感兴趣的话。
POJ 2195
技术网站地址： vmfor.com
相关文章
