首页 > 代码库 > UVALive 4043 转化最佳完美匹配

UVALive 4043 转化最佳完美匹配

2024-07-07 03:20:48   227人阅读

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

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

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

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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
struct node
{
    int x,y;
} n1[110],n2[110];
int n,S[110],T[110],lefts[110],rights[110];
double w[110][110],lx[110],ly[110];

bool eq(double a, double b) {
  return fabs(a-b) < 1e-9;
}

bool dfs(int u)
{
    S[u]=1;
    for (int v=1;v<=n;v++)if(eq(lx[u]+ly[v],w[u][v]) && !T[v]){
        T[v]=1;
        if (!lefts[v]|| dfs(lefts[v])){
            lefts[v]=u;
            rights[u]=v;
            return true;
        }
    }
    return false;
}
void up()
{
    double a=1e30;
    for (int i=1;i<=n;i++) if (S[i])
      for (int j=1;j<=n;j++) if (!T[j])
    {
        a=min(a,lx[i]+ly[j]-w[i][j]);
    }
    for (int i=1;i<=n;i++){
        if (S[i]) lx[i]-=a;
        if (T[i]) ly[i]+=a;
    }
}
void KM()
{
    int i,j;
    for (i=1;i<=n;i++){
        lefts[i]=lx[i]=ly[i]=0;
        for (j=1;j<=n;j++){
            lx[i]=max(lx[i],w[i][j]);
        }
    }
    for (i=1;i<=n;i++){
        for (;;){
            memset(S,0,sizeof S);
            memset(T,0,sizeof T);
            if (dfs(i)) break; else up();
        }
    }
}
int main()
{
    while (scanf("%d",&n)!=EOF)
    {
        for (int i=1;i<=n;i++) scanf("%d%d",&n1[i].x,&n1[i].y);
        for (int i=1;i<=n;i++) scanf("%d%d",&n2[i].x,&n2[i].y);
        for (int i=1;i<=n;i++)
            for (int j=1;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=1;i<=n;i++)
            printf("%d\n",rights[i]);
    }
    return 0;
}

 


联系
我们