UVA1411 Ants

题意

给出黑点白点各 $n(\le 100)$ 个，要求一个黑点连接一个白点，并且所有线段都不相交。

题解

所有线段不相交 $\rightarrow$ 两两连最近的点 。

那么把距离变成负数就是KM算法裸题了，但这道题有个神奇的坑点：如果在 find() 里更新顶标的偏移值 d ，就会T；而改在外面更新就A了。我也不知道为什么，看来以后得改下KM算法的写法了。

#include<bits/stdc++.h>
#define eps 1e-4
#define pdd pair<double,double>
#define fi first
#define se second

using namespace std;

const int N=105;
int n,mch[N];
pdd a[N],b[N];
bool lv[N],rv[N];
double d,l[N],r[N],dis[N][N];

inline double getDis(pdd x,pdd y)
{
    double dx=x.first-y.first,dy=x.second-y.second;
    return sqrt(dx*dx+dy*dy);
}

bool find(int x)
{
    lv[x]=1;
    for (int y=1;y<=n;y++)
    {
        if (rv[y]) continue;
        if (fabs(l[x]+r[y]-dis[x][y])<eps)
        {
            rv[y]=1;
            if (!mch[y] || find(mch[y])) return mch[y]=x,1;
        }
        //else d=min(d,l[x]+r[y]-dis[x][y]); 如果在这更新就会T
    }
    return 0;
}

inline void km()
{
    memset(l,0,sizeof(l));
    memset(r,0,sizeof(r));
    memset(mch,0,sizeof(mch));
    for (int i=1;i<=n;i++)
    {
        for (;;)
        {
            memset(lv,0,sizeof(lv));
            memset(rv,0,sizeof(rv));
            d=1e9;
            if (find(i)) break;
            for (int i=1;i<=n;i++) //在外面更新
            {
                if (!lv[i]) continue;
                for (int j=1;j<=n;j++)
                {
                    if (rv[j]) continue;
                    d=min(d,l[i]+r[j]-dis[i][j]);
                }
            }
            for (int j=1;j<=n;j++)
            {
                if (lv[j]) l[j]-=d;
                if (rv[j]) r[j]+=d;
            }
        }
    }
}

signed main()
{
    while (scanf("%d",&n)!=EOF)
    {
        for (int i=1;i<=n;i++) scanf("%lf%lf",&a[i].fi,&a[i].se);
        for (int i=1;i<=n;i++)
        {
            scanf("%lf%lf",&b[i].fi,&b[i].se);
            for (int j=1;j<=n;j++) dis[i][j]=-getDis(b[i],a[j]);
        }
        km();
        for (int i=1;i<=n;i++) printf("%d\n",mch[i]);
    }
    return 0;
}