[置顶] Ants(Northeastern Europe 2007)

5
-42 58
44 86
7 28
99 34
-13 -59
-47 -44
86 74
68 -75
-68 60
99 -60

4
2
1
5
3

在暑假集训结束的最后两天再学习一个新的算法，来满足一下自己的成就感。。哈哈！！！

但是有好多不理解是为什么，希望理解的大牛，大神可以解释一下。

题意：

题目的意思就是说有一个蚂蚁军团，想爬上苹果树吃苹果。然后题目会先给你一个n代表蚂蚁军团和苹果树各有n个。然后叫你通过计算而确定如何连接。

从题目中可以看到，苹果树和蚂蚁分别分成了两个部分。因此，可以轻松的想到了二分匹配问题。

然后就可以根据数学几何的知识，如果a1–b1与a2–b2相交，那么dist(a1,b1)+dist(a2,b2)一定大于dist(a1,b2)+dist(a2,b1),因为三角形的两边之和大于第三边。因此可得知最佳匹配中不会出现线段相交的情况。

还要注意输出的时候，因为是树按照从1–n输出的所以要进行转换后再输出。

题目意思如果知道了会，但不知细节问题的话，那就看下面的两个代码吧。

一个是O（n^4）的KM(   ),（还有一个是经过松弛处理的KM（）；不过非本人原创）。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#define CL(x,v);memset(x,v,sizeof(x));
#define maxn 105
#define INF 1000000
using namespace std;int Left[maxn],n;
bool S[maxn],T[maxn];
double Lx[maxn],Ly[maxn],w[maxn][maxn];
struct Point
{
    double x,y;
}p[maxn*2];double Dist(Point a,Point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool match(int i)
{
    S[i] = true;
    for(int j = 1;j <= n;j++)
      if(fabs(Lx[i]+Ly[j]-w[i][j])<1e-5&&!T[j])
      {
          T[j] = true;
          if(!Left[j]||match(Left[j])){
             Left[j] = i;
             return true;
          }
      }
    return false;
}
 //    没有这个函数，则就是稳定婚姻模型了。
void update()
{
    double a = INF;
    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()
{
    CL(Left,0);CL(Lx,0);CL(Ly,0);
    for(int i = 1;i <= n;i++)
      for(int j = 1;j <= n;j++)
        Lx[i] = max(Lx[i],w[i][j]);
    for(int i = 1;i <= n;i++){
       while(1){
         CL(S,0); CL(T,0);
         if(match(i)) break;
         else update();
       }
    }
}
int main()
{
    while(cin>>n)
    {
        for(int i = 1;i <= 2*n;i++)
          cin>>p[i].x>>p[i].y;
        for(int i = 1;i <= n;i++)
          for(int j = 1;j <= n;j++)
            w[i][j] = -Dist(p[i],p[j+n]);  //这里为嘛？加一个负号。
        KM();                              //哪位大牛，大神知道的请告诉一下哈
        int tree[maxn];
        for(int i = 1;i <= n;i++)
          tree[Left[i]] = i;
        for(int i = 1;i <= n;i++)
          cout<<tree[i]<<endl;
    }
    return 0;
}