题意:给出N个白点和N个黑点,要求用N条不相交的线段把它们连接起来,其中每条线段恰好连接一个白点和一个黑点,每个点恰好连接到一条线段。
分析:因为有结点黑白两色,我们不难想到构造一个二分图,其中每个白点对应一个X结点,每个黑点对应一个Y结点,每个黑点和每个白点相连,权值等于二者的欧几里德距离。建模后最佳完美匹配就是问题的解。为什么呢?假设在最佳完美匹配中有两条线段a1-b1与a2-b2相交,那么dist(a1,b1)+dist(a2,b2)一定大于dist(a1,b2)+dist(a2,b1),因此如果把这两条改成a1-b2和a2-b1后总长度会变少,与最佳二字矛盾。
注意:KM算法是求权值和最大的,故需要将距离边成负数即可。并且输入坐标值好像是浮点的。
参考自:http://www.cnblogs.com/arbitrary/archive/2013/02/27/2936008.html
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define Del(x,y) memset(x,y,sizeof(x))
#define N 105
#define INF 999999999
struct Point
{
double x,y;
} point[N*];double dis(Point a,Point b)
{
return sqrt((double)((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
}double lx[N],ly[N]; //顶点标号
int link[N]; //存放与T点集连结的S点集里的点
int S[N],T[N]; //visit,是否属于相等子图
double w[N][N];
int n;bool match(int i) //匈牙利
{
S[i]=true;
for(int j=;j<=n;j++)
{
if(abs(lx[i]+ly[j]-w[i][j])<10e-&&!T[j])
{
T[j]=true;
if(link[j]==||match(link[j]))
{
link[j]=i;
return true;
}
}
}
return false;
}void update() //更新顶点标号
{
double a=INF;
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; //S集里的点-a
if(T[i]) ly[i]+=a; //T集里的点+a
} //其余所有点不变
}void KM()
{
for(int i=; i<=n; i++)
{
link[i]=lx[i]=ly[i]=;
for(int j=; j<=n; j++)
lx[i]=max(lx[i],w[i][j]);
}
for(int i=; i<=n; i++)
for(;;)
{
Del(S,);
Del(T,);
if(match(i))break;
else update();
}
}int ans[N];int main()
{
scanf("%d",&n);
for(int i=; i<=n*; i++)
scanf("%lf%lf",&point[i].x,&point[i].y);
for(int i=; i<=n; i++)
for(int j=; j<=n; j++)
w[i][j]=-dis(point[i],point[j+n]);
KM();
for(int i=;i<=n;i++)
ans[link[i]]=i;
for(int i=;i<=n;i++)
printf("%d\n",ans[i]);
return ;
}