POJ 3565 Ants (证明+KM算法)

思路：由于最佳匹配不会存在相交情况、于是直接KM算法、由于是小数、注意精度误差、KM算法求的是最大权值和、所以将所有边变负、便可以求出最小权值和

自己写的第一道KM、、、、mark

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define eps 1e-4
struct node
{
    double x,y;
}dot1[105],dot2[105];
int n;
double mpt[105][105];
int match[105];
double lx[105];
double ly[105];
bool visitx[105];
bool visity[105];
double dist(node a,node b)
{
    return -sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int hungary(int x)
{
    visitx[x]=true;
    for(int i=1;i<=n;i++)
    {
        if(!visity[i]&&fabs(lx[x]+ly[i]-mpt[x][i])<eps)
        {
            visity[i]=true;
            if(match[i]==-1||hungary(match[i]))
            {
                match[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
void KM_perfect_match()
{
    memset(match,-1,sizeof(match));
    memset(lx,0,sizeof(lx));
    memset(ly,0,sizeof(ly));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            lx[i]=max(lx[i],mpt[i][j]);
    for(int i=1;i<=n;i++)
    {
        while(1)
        {
            memset(visitx,false,sizeof(visitx));
            memset(visity,false,sizeof(visity));
            if(hungary(i))break;//匹配成功
            else//匹配失败，找最小值
            {
                double temp=0x3f3f3f;
                for(int j=1;j<=n;j++)
                {
                    if(visitx[j])
                    {
                        for(int k=1;k<=n;k++)
                        {
                            if(!visity[k]&&temp>(lx[j]+ly[k]-mpt[j][k]))
                                temp=lx[j]+ly[k]-mpt[j][k];
                        }
                    }
                }
                for(int j=1;j<=n;j++)
                {
                    if(visitx[j])
                        lx[j]-=temp;
                    if(visity[j])
                        ly[j]+=temp;
                }
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&dot1[i].x,&dot1[i].y);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%lf",&dot2[i].x,&dot2[i].y);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            mpt[i][j]=dist(dot1[i],dot2[j]);
        }
    }
    KM_perfect_match();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(match[j]==i)
            {
                printf("%d\n",j);
                break;
            }
        }
    }
    return 0;
}

POJ 3565 Ants (证明+KM算法),布布扣,bubuko.com

POJ 3565 Ants (证明+KM算法)

原文：http://blog.csdn.net/a1dark/article/details/24287667