UVA1411 Ants

想出的一道题竟然是原题QAQ

非常有趣的一个题

根据三角形两边之和大于第三边所以相交的线段一定是比不相交的线段要长的

所以直接二分图构图最小费用最大流即可

（我不管我不管我要把这个出到NOIP膜你赛）

代码如下。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<queue>

#define inf 20021225

#define ll long long

#define db double

#define mxn 400

#define eps 1e-6

using namespace std;

struct edge{int to,lt,f,fr;db c;}e[mxn*mxn];

struct point{int x,y;}p[mxn];

int in[mxn],from[mxn],cnt=1,nn,s,t,n,m;

db dis[mxn],ans;bool vis[mxn];

void add(int x,int y,int f,db c)

{

	e[++cnt].to=y;e[cnt].lt=in[x];e[cnt].f=f;e[cnt].fr=x;e[cnt].c=c;in[x]=cnt;

	e[++cnt].to=x;e[cnt].lt=in[y];e[cnt].f=0;e[cnt].fr=y;e[cnt].c=-c;in[y]=cnt;

}

queue<int> que;

bool spfa()

{

	for(int i=1;i<=nn;i++)	dis[i]=inf,vis[i]=0;

	vis[s]=1;dis[s]=0.0;que.push(s);

	while(!que.empty())

	{

		int x=que.front();que.pop();vis[x]=0;

		//printf("%d ",x);

		for(int i=in[x];i;i=e[i].lt)

		{

			int y=e[i].to;

			if(e[i].f&&dis[y]>dis[x]+e[i].c)

			{

				dis[y]=dis[x]+e[i].c;

				from[y]=i;

				if(!vis[y])	que.push(y),vis[y]=1;

			}

		}

	}

	//printf("%lf %lf\n",dis[t],inf+eps);

	return dis[t]<inf-eps;

}

db flow()

{

	int flow=inf;

	for(int i=t;i!=s;i=e[from[i]].fr)	flow=min(flow,e[from[i]].f);

	for(int i=t;i!=s;i=e[from[i]].fr)	e[from[i]].f-=flow,e[from[i]^1].f+=flow;

	return flow*dis[t];

}

void dinic()

{

	while(spfa())	ans+=flow();

}

db dist(point a,point b)

{

	return sqrt((db)(a.x-b.x)*(a.x-b.x)+(db)(a.y-b.y)*(a.y-b.y));

}

int main()

{

	while(scanf("%d",&n)!=EOF)

	{

		cnt=1;memset(in,0,sizeof(in));

		s=n*2+1;t=s+1;nn=t;

		for(int i=1;i<=2*n;i++)	scanf("%d%d",&p[i].x,&p[i].y);

		for(int i=1;i<=n;i++)	add(s,i,1,0),add(i+n,t,1,0);

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

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

				add(i,j+n,1,dist(p[i],p[j+n]));

		dinic();

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

			for(int j=in[i];j;j=e[j].lt)

				if(!e[j].f)

				{

					printf("%d\n",e[j].to-n);

					break;

				}

	}

	return 0;

}

巴特西

UVA1411 Ants

最新文章

热门文章