POJ 2195 Going Home(二分图最优匹配)

POJ 2195 Going Home(二分图最优匹配)

http://poj.org/problem?id=2195

题意:

给定一个N*M的地图，地图上有若干个man和house，且man与house的数量一致。man每移动一格需花费$1（即单位费用=单位距离），一间house只能入住一个man。现在要求所有的man都入住house，求最小费用。

分析:

每个人对应二分图左边的点,每个房间对应二分图右边的点.每个人与每个房间都有一条带权值的边,表示这个人到该房间的花费.

为了使得每个人都得到一个房间,且他们行走的开销最小.

那么本题求得就是该二分图的一个完备匹配且该匹配边的权值和最小了.

但是KM算法只能求二分图的最优匹配(即匹配边权值和最大的匹配),我们现在要求权值和最小的匹配怎么办?

我们只需要把所有边的权值取负即可(确实是这么操作,但是如果想严谨的证明这个结论的话,我感觉不太好证).最终用KM算法求出的就是我们所需的最小权值匹配的负数.

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100+5;

struct Max_Match
{
    int W[maxn][maxn],n;
    int Lx[maxn],Ly[maxn];
    bool S[maxn],T[maxn];
    int left[maxn];

    bool match(int i)
    {
        S[i]=true;
        for(int j=1;j<=n;j++)if(Lx[i]+Ly[j]==W[i][j] && !T[j])
        {
            T[j]=true;
            if(left[j]==-1 || match(left[j]))
            {
                left[j]=i;
                return true;
            }
        }
        return false;
    }

    void update()
    {
        int a=1<<30;
        for(int i=1;i<=n;i++)if(S[i])
        for(int j=1;j<=n;j++)if(!T[j])
        {
            a = min(a,Lx[i]+Ly[j]-W[i][j]);
        }
        for(int i=1;i<=n;i++)
        {
            if(S[i]) Lx[i]-=a;
            if(T[i]) Ly[i]+=a;
        }
    }

    int solve(int n)
    {
        this->n=n;
        memset(left,-1,sizeof(left));
        for(int i=1;i<=n;i++)
        {
            Lx[i]=Ly[i]=0;
            for(int j=1;j<=n;j++)
                Lx[i]=max(Lx[i], W[i][j]);
        }

        for(int i=1;i<=n;i++)
        {
            while(true)
            {
                for(int j=1;j<=n;j++) S[j]=T[j]=false;
                if(match(i)) break;
                else update();
            }
        }

        int ans=0;
        for(int i=1;i<=n;i++) ans+= W[left[i]][i];
        return ans;
    }
}KM;

struct Node
{
    int x,y;
    Node(){}
    Node(int x,int y):x(x),y(y){}
}node1[maxn],node2[maxn];

int main()
{
    int R,C;
    while(scanf("%d%d",&R,&C)==2 && R)
    {
        int num1=0,num2=0;
        for(int i=1;i<=R;i++)
        for(int j=1;j<=C;j++)
        {
            char c;
            scanf(" %c",&c);
            if(c=='H') node2[++num2]=Node(i,j);
            else if(c=='m') node1[++num1]=Node(i,j);
        }

        for(int i=1;i<=num1;i++)
        for(int j=1;j<=num2;j++)
            KM.W[i][j]=-( abs(node1[i].x-node2[j].x)+abs(node1[i].y-node2[j].y) );//取负值
        int ans = KM.solve(num1);
        printf("%d\n",-ans);//取负值
    }
    return 0;
}