#include <iostream>
#include <cmath>
using namespace std;
double map[105][105];
int link[105];
bool vx[105],vy[105];
double lx[105],ly[105];
double lack;
const double Inf=99999999.0;
const double epx=1e-6;
int n;
struct node
{
       double x;
       double y;
}a[105],b[105];
double abs1(double x1)
{
       if (x1<0)return 0-x1;
       else return x1;
}
double dist(node p,node q)
{
      return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y));    
}
bool dfs(int v)
{
     vx[v]=true;
     double t;
     for (int i=1;i<=n;i++)
     {  
         if  (!vy[i])
         { 
               t=lx[v]+ly[i]-map[v][i];
               if (abs1(t)<=epx)
               {  
                  vy[i]=true;
                  if (link[i]==-1||dfs(link[i]))
                  {
                     link[i]=v;
                     return true;
                  } 
               }
               else lack=max(t,lack);
         }
     }
return false;
}
void KM()
{
    int i,j,k;
    for (i=1;i<=n;i++)
    {
        lx[i]=Inf;  
        for (j=1;j<=n;j++)
            lx[i]=min(lx[i],map[i][j]);
        ly[i]=0;
    }
    for (i=1;i<=n;i++)
    {
        while (1)
        { 
              memset(vx,0,sizeof(vx));
              memset(vy,0,sizeof(vy));
              lack=-Inf;
              if (dfs(i))break;
              for (j=1;j<=n;j++)
              {
                  if (vx[j])lx[j]=lx[j]-lack;
                  if (vy[j])ly[j]=ly[j]+lack;
              }
        }
    }
}
void init()
{
     for (int i=0;i<105;i++)
     {
         link[i]=-1;
         for (int j=0;j<105;j++)
             map[i][j]=0.0;
     }
}
int main()
{
    int i,j,k;
    while (scanf("%d",&n)!=EOF)
    {
          init();
          for (i=1;i<=n;i++)
              scanf("%lf%lf",&a[i].x,&a[i].y);
          for (i=1;i<=n;i++)
              scanf("%lf%lf",&b[i].x,&b[i].y);     
          for (i=1;i<=n;i++)
          for (j=1;j<=n;j++)
              map[i][j]=dist(a[i],b[j]);
          KM();
          for (i=1;i<=n;i++)
          for (j=1;j<=n;j++)
          if (link[j]==i)
          {
              printf("%d\n",j);
              break;
          }
    }
return 0;
}

• Re:KM()为什么这样写超时？求解释~~ (103) dingjian0312 2011-12-07 17:18:06
• Re:KM()为什么这样写超时？求解释~~ (45) xc19881023 2016-04-27 16:28:05
  • Re:KM()为什么这样写超时？求解释~~ (48) xc19881023 2016-04-27 16:50:19