首页 > 代码库 > 【POJ3565】ANTS KM算法

【POJ3565】ANTS KM算法

2024-09-18 07:44:43   219人阅读

【POJ3565】ANTS

题意：平面上有2*n个点，N白N黑。为每个白点找一个黑点与之连边，最后所有边不交叉。求一种方案。

题解：KM算法真是一个神奇的算法，虽然感觉KM能做的题用费用流都能做~

本题用到的结论：当选出的点对之间的距离之和最小时，一定使所有边都不交叉

这个感觉很容易理解，自己画画图就能看出来，就是难想啊

然后跑最小权值匹配，方法是将边权都变成相反数，然后跑最大权值匹配

不知道为什么以前写的KM算法会TLE，将求temp的过程拿到主函数里就过了

#include <cstdio>#include <cstring>#include <iostream>#include <cmath>using namespace std;int n;int xa[110],ya[110],xb[110],yb[110],va[110],vb[110],from[110],sta[110];double dis[110][110],la[110],lb[110],temp;int dfs(int x){	va[x]=1;	for(int i=1;i<=n;i++)	{		if(!vb[i]&&fabs(la[x]+lb[i]-dis[x][i])<1e-6)		{			vb[i]=1;			if(!from[i]||dfs(from[i]))			{				from[i]=x;				return 1;			}		}	}	return 0;}int main(){	scanf("%d",&n);	int i,j,k;	for(i=1;i<=n;i++)	scanf("%d%d",&xa[i],&ya[i]);	for(i=1;i<=n;i++)	scanf("%d%d",&xb[i],&yb[i]);	for(i=1;i<=n;i++)		for(j=1;j<=n;j++)			dis[i][j]=-sqrt(1.0*(xa[i]-xb[j])*(xa[i]-xb[j])+(ya[i]-yb[j])*(ya[i]-yb[j]));	for(i=1;i<=n;i++)		for(j=2,la[i]=dis[i][1];j<=n;j++)			la[i]=max(la[i],dis[i][j]);	for(i=1;i<=n;i++)	{		while(1)		{			memset(va,0,sizeof(va));			memset(vb,0,sizeof(vb));			temp=99999999.999999;			if(dfs(i))	break;			for(j=1;j<=n;j++)	if(va[j])				for(k=1;k<=n;k++)	if(!vb[k])					temp=min(temp,la[j]+lb[k]-dis[j][k]);			for(j=1;j<=n;j++)	if(va[j])	la[j]-=temp;			for(j=1;j<=n;j++)	if(vb[j])	lb[j]+=temp;		}	}	for(i=1;i<=n;i++)	sta[from[i]]=i;	for(i=1;i<=n;i++)	printf("%d\n",sta[i]);	return 0;}

【POJ3565】ANTS KM算法


联系
我们