POJ 2195 二分图最小权婚配KM算法

POJ 2195 二分图最小权匹配KM算法

本来是打算昨天晚上写的，昨天网速渣的连CSDN都进不去，没办法只能现在来写了

先写写对KM算法的理解，KM算法是对每个点设置一个顶标，只有当边长等于两边点的顶标之和的时候才进行增广，这样就能保证得到的一定是最大权匹配。

如果找不到匹配的时候就对交替路中X集合的顶标减少一个d Y集合的顶标增加一个d。

这样两个点都在交替路中的时候x[i]+y[i]的和不边

X在 Y不在的时候x[i]+y[i]减少，可能就会为图增加一对匹配。

X不在Y在的时候x[i]+y[i]增加，原来不在现在依然不在其中。

题意：有n个人n个房子，每人进一个房子，求最少的总距离。

思路：对每条边取相反数，然后得到的结果再取相反数，就能得到最小权匹配。

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#include<math.h>
#include<iostream>
#define INF 10000000
using namespace std;
char map[105][105];
struct point{
   int x,y;
}X[105],Y[105];
int W[105][105];
int macy[105];
bool check[105];
bool checkx[105];
int zx[105];
int zy[105];
int Y1[105];
int n;
bool dfs(int u)
{
    checkx[u]=1;
    for(int i=0;i<n;i++)
    {
        if(zx[u]+zy[i]==W[u][i]&&!check[i])
        {
            check[i]=1;
            if(macy[i]==-1||dfs(macy[i]))
            {
                macy[i]=u;
                return 1;
            }
        }
        if(!check[i])
        {
            Y1[i]=min(Y1[i],zx[u]+zy[i]-W[u][i]);
        }
    }
    return 0;
}
void gx()
{
    int a=INF;
    for(int i=0;i<n;i++)
        if(!check[i])
        a=min(a,Y1[i]);
    for(int i=0;i<n;i++)
    {
        if(check[i]) zy[i]+=a;
        if(checkx[i]) zx[i]-=a;
    }
}
void xyl()
{
    memset(macy,-1,sizeof(macy));
    for(int i=0;i<n;i++)
    {
        memset(check,0,sizeof(check));
        memset(checkx,0,sizeof(checkx));
        if(!dfs(i))
        {
            i--;
            gx();
        }
    }
}
int main()
{
    int N,M;
    while(scanf("%d%d",&N,&M)!=EOF)
    {
        if(N==0&&M==0) return 0;
        for(int i=0;i<N;i++)
            scanf("%s",map[i]);
            int r1=0,r2=0;
        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++)
        {
            if(map[i][j]=='H')
            {
                X[r1].x=i;
                X[r1].y=j;
                r1++;
            }
            else if(map[i][j]=='m')
            {
                Y[r2].x=i;
                Y[r2].y=j;
                r2++;
            }
        }
        memset(zy,0,sizeof(zy));
        for(int i=0;i<r1;i++)
       {
           zx[i]=-INF;
           for(int j=0;j<r2;j++)
            {
                W[i][j]=abs(X[i].x-Y[j].x)+abs(X[i].y-Y[j].y);
                W[i][j]*=-1;
                zx[i]=max(zx[i],W[i][j]);
                Y1[j]=INF;
            }
       }
        n=r1;
        //return 0;
        xyl();
        int p=0;
        for(int i=0;i<n;i++)
        {
            int u=macy[i];
            p+=W[u][i];
        }
        printf("%d\n",-p);
    }
}

POJ 2195 二分图最小权婚配KM算法

相关推荐