UVALive 4043 转化最佳完美匹配

首先黑点和白点是组成一个二分图这毫无疑问

关键是题目中要求的所有黑白配的线不能交叉。。。一开始我也没想到这个怎么转化为二分图里面的算法。

后来看书才知道，如果两两交叉，则可以把两根线当四边形的对角线，连四边形的两条边，则肯定不交叉，而且一个很明显的特征是，不交叉的两条线的他们的长度和一定比交叉线的长度和小。

于是我们只要求出最小长度的线，就必定是不相交的。那就要用到最佳完美匹配了，首先算出两两点的欧几里得距离，然后取负数，这样走一遍匹配，得到的必定是最短的欧几里得距离，即不相交的线

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

struct node

{

    int x,y;

} n1[],n2[];

int n,S[],T[],lefts[],rights[];

double w[][],lx[],ly[];

bool eq(double a, double b) {

  return fabs(a-b) < 1e-;

}

bool dfs(int u)

{

    S[u]=;

    for (int v=;v<=n;v++)if(eq(lx[u]+ly[v],w[u][v]) && !T[v]){

        T[v]=;

        if (!lefts[v]|| dfs(lefts[v])){

            lefts[v]=u;

            rights[u]=v;

            return true;

        }

    }

    return false;

}

void up()

{

    double a=1e30;

    for (int i=;i<=n;i++) if (S[i])

      for (int j=;j<=n;j++) if (!T[j])

    {

        a=min(a,lx[i]+ly[j]-w[i][j]);

    }

    for (int i=;i<=n;i++){

        if (S[i]) lx[i]-=a;

        if (T[i]) ly[i]+=a;

    }

}

void KM()

{

    int i,j;

    for (i=;i<=n;i++){

        lefts[i]=lx[i]=ly[i]=;

        for (j=;j<=n;j++){

            lx[i]=max(lx[i],w[i][j]);

        }

    }

    for (i=;i<=n;i++){

        for (;;){

            memset(S,,sizeof S);

            memset(T,,sizeof T);

            if (dfs(i)) break; else up();

        }

    }

}

int main()

{

    while (scanf("%d",&n)!=EOF)

    {

        for (int i=;i<=n;i++) scanf("%d%d",&n1[i].x,&n1[i].y);

        for (int i=;i<=n;i++) scanf("%d%d",&n2[i].x,&n2[i].y);

        for (int i=;i<=n;i++)

            for (int j=;j<=n;j++){

                w[i][j]=(double)(n1[i].x-n2[j].x)*(n1[i].x-n2[j].x)+(double)(n1[i].y-n2[j].y)*(n1[i].y-n2[j].y);

                w[i][j]=-sqrt(w[i][j]);

            }

        KM();

        for (int i=;i<=n;i++)

            printf("%d\n",rights[i]);

    }

    return ;

}

巴特西

UVALive 4043 转化最佳完美匹配

最新文章

热门文章