poj 3565 二分图最优匹配

思路:

将ant与tree之间用距离来做权值,求最小权匹配就可以了。可以想到,如果有两条线段相交,那么将这两个线段交换一个顶点,使其不相交,其权值和一定会更小。

就像斜边永远比直角边长一样的道理。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define Maxn 110
#define Eps 0.000001
using namespace std;
int sx[Maxn],sy[Maxn],match[Maxn],n;
double lx[Maxn],ly[Maxn],weight[Maxn][Maxn],slack[Maxn];
struct Point{
double x,y;
}tree[Maxn],ant[Maxn];
double Dis(Point a,Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int dfs(int u)
{
int i;
sx[u]=;
for(i=;i<=n;i++)
{
if(!sy[i]&&(lx[u]+ly[i]-weight[u][i]<Eps))
{
sy[i]=;
if(match[i]==-||dfs(match[i]))
{
match[i]=u;
return ;
}
}
if(!sy[i]&&slack[i]>lx[u]+ly[i]-weight[u][i])
slack[i]=lx[u]+ly[i]-weight[u][i];
}
return ;
}
int bestmatch()
{
int i,j;
for(i=;i<=n;i++)
{
lx[i]=-;
ly[i]=;
for(j=;j<=n;j++)
{
weight[i][j]=-weight[i][j];
lx[i]=max(lx[i],weight[i][j]);
}
}
memset(match,-,sizeof(match));
//cout<<n<<endl;
for(i=;i<=n;i++)
{
for(j=;j<=n;j++)
slack[j]=;
while()
{
memset(sx,,sizeof(sx));
memset(sy,,sizeof(sy));
if(dfs(i))
break;
double dx=;
for(j=;j<=n;j++)
if(!sy[j])
dx=min(dx,slack[j]);//每次找的都是不在交错路径上的点,故slack[i]==0的情况不会被遍历
for(j=;j<=n;j++)
{
if(sx[j])
lx[j]-=dx;
if(sy[j])
ly[j]+=dx;
else
slack[j]-=dx;//由于X(i)已经更新过了,故每个slack[i]要减去dx,否则下次循环就会多减
}
}
}
int ans=;
for(i=;i<=n;i++)
ans+=weight[match[i]][i];
return -ans;
}
int main()
{
int i,j;
while(scanf("%d",&n)==)
{
for(i=;i<=n;i++)
scanf("%lf%lf",&ant[i].x,&ant[i].y);
for(i=;i<=n;i++)
scanf("%lf%lf",&tree[i].x,&tree[i].y);
for(i=;i<=n;i++)
for(j=;j<=n;j++)
weight[i][j]=Dis(tree[i],ant[j]);
bestmatch();
for(i=;i<=n;i++)
printf("%d\n",match[i]);
}
return ;
}
上一篇:hdu 1573 X问题 不互质的中国剩余定理


下一篇:javamail 利用qq邮箱做邮箱服务器,简单小demo