POJ3565

题目大意：

给定\(n\)个蚂蚁和\(n\)颗苹果树的坐标，要求每个蚂蚁爬到一颗苹果树旁，使得每个蚂蚁路线不相交且路线总长度最小，求每个蚂蚁爬到哪个苹果树旁？

首先假设有两只蚂蚁路径相交，那么这两个蚂蚁交换目标一定使得总路线缩短且不相交，所以总长度最短时所有蚂蚁路线一定不相交

怎么让总路线最短呢？二分图最小权匹配

其实只要把边权全部取反然后跑最大权匹配就好了

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

namespace red{

#define int long long

#define eps (1e-6)

	inline int read()

	{

		int x=0;char ch,f=1;

		for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());

		if(ch=='-') f=0,ch=getchar();

		while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

		return f?x:-x;

	}

	const int N=210;

	int n;

	struct node

	{

		int x,y;

	}ant[N],tr[N];

	double jx[N][N];

	inline int sqr(int x){return x*x;}

	inline double dis(int i,int j)

	{

		return sqrt(sqr(ant[i].x-tr[j].x)+sqr(ant[i].y-tr[j].y));

	}

	double exl[N],exr[N],slack[N];

	bool visl[N],visr[N];

	int f[N],g[N];

	inline bool find(int x)

	{

		visl[x]=1;

		for(int y=1;y<=n;++y)

		{

			if(visr[y]) continue;

			double tmp=exl[x]+exr[y]-jx[x][y];

			if(fabs(tmp)<eps)

			{

				visr[y]=1;

				if(!f[y]||find(f[y]))

				{

					f[y]=x;

					g[x]=y;

					return 1;

				}

			}

			else slack[y]=min(tmp,slack[y]);

		}

		return 0;

	}

	inline void km()

	{

		for(int i=1;i<=n;++i)

		{

			exl[i]=jx[i][1];

			for(int j=2;j<=n;++j)

			{

				exl[i]=max(exl[i],jx[i][j]);

			}

		}

		for(int i=1;i<=n;++i)

		{

			for(int j=1;j<=n;++j)

			{

				visl[j]=visr[j]=0;

				slack[j]=1e9+7;

			}

			if(find(i)) continue;

			while("haku")

			{

				double tmp=1e9+7;

				int t;

				for(int j=1;j<=n;++j)

					if(!visr[j]) tmp=min(tmp,slack[j]);

				for(int j=1;j<=n;++j)

				{

					if(visl[j]) exl[j]-=tmp;

					if(visr[j]) exr[j]+=tmp;

					else

					{

						slack[j]-=tmp;

						if(fabs(slack[j])<eps) t=j;

					}

				}

				if(!f[t]) break;

				visr[t]=1,visl[f[t]]=1;

				t=f[t];

				for(int j=1;j<=n;++j)

					slack[j]=min(slack[j],exl[t]+exr[j]-jx[t][j]);

			}

			memset(visl,0,sizeof(visl));

			memset(visr,0,sizeof(visr));

			find(i);

		}

		for(int i=1;i<=n;++i) printf("%lld\n",g[i]);

	}

	inline void main()

	{

		while(~scanf("%lld",&n))

		{

			memset(f,0,sizeof(f));

			memset(g,0,sizeof(g));

			memset(exl,0,sizeof(exl));

			memset(exr,0,sizeof(exr));

			for(int i=1;i<=n;++i)

			{

				ant[i].x=read(),ant[i].y=read();

			}

			for(int i=1;i<=n;++i)

			{

				tr[i].x=read(),tr[i].y=read();

			}

			for(int i=1;i<=n;++i)

			{

				for(int j=1;j<=n;++j)

				{

					jx[i][j]=-dis(i,j);

				}

			}

			km();

		}

	}

}

signed main()

{

	red::main();

return 0;

}

巴特西

POJ3565

最新文章

热门文章