POJ-3565-Ants(二分图最优匹配)

Ants

题意：

• 个蚂蚁群，棵苹果树，怎样分配(一对一分配)使得它们直接没有交集？

思路：

• 
  如图根据三角形三边关系可以得出。
• 这个是找最小权值的最优分配。我们已经会最大权值的最优匹配了，怎样找最小匹配呢？把权值改成对应的负值，我们之前的最大匹配求出的的权值就不是最小的值了，那把负值的最大匹配求出来就不是正值的最小值了哈哈哈哈
  注意：scalk数组是double，不能使用memset函数赋值INF

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define INF 0x3f3f3f3f
using namespace std;
const double esp=1e-6;
struct node
{
    double x,y;
} pointant[110],pointtree[110];
double edge[110][110];
double exant[110];
double extree[110];
int visant[110];
int vistree[110];
int match[110];
double scalk[110];
int n;
bool Hungarian(int tree)
{
    vistree[tree]=1;
    for(int ant=1; ant<=n; ant++)
    {
        if(visant[ant])
        {
            continue;
        }
        double tep=exant[ant]+extree[tree]-edge[tree][ant];
        if(abs(tep)<esp)
        {
            visant[ant]=1;
            if(match[ant]==-1||Hungarian(match[ant]))
            {
                match[ant]=tree;
                return true;
            }
        }
        else
        {
            if(tep<scalk[ant])
            {
                scalk[ant]=tep;
            }

        }
    }
    return false;
}
void KM( )
{
    memset(match,-1,sizeof(match));
    memset(exant,0,sizeof(exant));
    for(int i=1; i<=n; i++)
    {
        extree[i]=edge[i][1];
        for(int j=2; j<=n; j++)
        {
            if(edge[i][j]>extree[i])
            {
                extree[i]=edge[i][j];
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=1;j<=n;j++)//double不能用memset函数赋值INF
        {
            scalk[j]=INF;
        }
        while(1)
        {
            memset(visant,0,sizeof(visant));
            memset(vistree,0,sizeof(vistree));
            if(Hungarian(i))
            {
                break;
            }
            //cout<<"flag"<<endl;
            double d=INF;
            for(int j=1; j<=n; j++)
            {
                if(!visant[j])
                {
                    if(d>scalk[j])
                    {
                        d=scalk[j];
                    }
                }
            }
            for(int j=1; j<=n; j++)
            {
                if(vistree[j])
                {
                    extree[j]-=d;
                }
                if(visant[j])
                {
                    exant[j]+=d;
                }
                else
                {
                    scalk[j]-=d;
                }

            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        printf("%d\n",match[i]);
    }
    return ;
}
double add(node a,node b)
{
    return -sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));//把正值改成负的
}
int main( )
{
    while(~scanf("%d",&n))
    {
        for(int i=1; i<=n; i++)
        {
            scanf("%lf%lf",&pointant[i].x,&pointant[i].y);
        }
        for(int i=1; i<=n; i++)
        {
            scanf("%lf%lf",&pointtree[i].x,&pointtree[i].y);
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                edge[i][j]=add(pointtree[i],pointant[j]);
            }
        }
        KM( );
    }
    return 0;
}