【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算法

【POJ3565】ANTS

最新文章

热门文章