首页 > 代码库 > 151. [USACO Dec07] 建造路径

151. [USACO Dec07] 建造路径

2024-10-24 03:01:02   210人阅读

★★   输入文件：roads.in   输出文件：roads.out   简单对比

时间限制：1 s   内存限制：128 MB

译 by CmYkRgB123

描述

Farmer John 刚刚得到了几个新农场！他想把这几个农场用路连接起来，这样他就可以通过笔直的公路从一个农场到另一个农场了。现在已经有了几条连接着的农场。

N (1 ≤ N ≤ 1,000) 个农场中，每个农场的位置在坐标平面的 (Xi, Yi) (0 ≤ Xi ≤ 1,000,000; 0 ≤ Yi ≤ 1,000,000)。已经有 M (1 ≤ M ≤ 1,000) 条路以前就被建好了。请你帮助 Farmer John 考虑建设尽量少长度的额外的路，使他的农场连在一起。

输入

* 第 1 行: 两个整数: N , M
* 第 2..N+1 行: 两个整数 Xi , Yi
* 第 N+2..N+M+2 行: 两个整数: i , j, 表示已经存在从农场i到农场j的路。

输出

* 第 1 行: 额外的路的最少长度，保留2小数。 请使用 64 位的浮点数。

样例输入

 4 1
 1 1
 3 1
 2 3
 4 3
 1 4

样例输出

 4.00

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>

using namespace std;
const int N=1010;

bool vis[N][N];
int fa[N];
int n,m,js,xx,yy,tot,total;
double answer;
struct node{
	double x,y;
}E[N];
struct NODE{
	int st,ed;
	double dis;
}EE[500000];

inline int read()
{
	int x=0;char c=getchar();
	while(c<‘0‘||c>‘9‘)c=getchar();
	while(c>=‘0‘&&c<=‘9‘)x=x*10+c-‘0‘,c=getchar();
	return x;
}

inline double calc(int a,int b)
{
	return sqrt(abs(E[a].x-E[b].x)*abs(E[a].x-E[b].x)+abs(E[a].y-E[b].y)*abs(E[a].y-E[b].y));
}

bool cmp(NODE a,NODE b)
{
	return a.dis<b.dis;
}

int getfa(int x)
{
	return fa[x]==x?x:fa[x]=getfa(fa[x]);
}

int main()
{
	freopen("roads.in","r",stdin);
	freopen("roads.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++)
		fa[i]=i,scanf("%lf%lf",&E[i].x,&E[i].y);
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			EE[++js].st=i,
			EE[js].ed=j,
			EE[js].dis=calc(i,j);
	
	for(int i=1;i<=m;i++)
		xx=read(),
		yy=read(),
		vis[xx][yy]=vis[yy][xx]=1;
	
	for(int i=1;i<=js;i++)
		if(vis[EE[i].st][EE[i].ed])
		{
			int fx=getfa(EE[i].st);
			int fy=getfa(EE[i].ed);
			fa[fx]=fy;
			EE[i].dis=double(N<<4);
		}	
	tot=n-1-m;
	sort(EE+1,EE+js+1,cmp);
	for(int i=1;i<=js;i++)
	{
		int fx=getfa(EE[i].st);
		int fy=getfa(EE[i].ed);
		if(fx!=fy)
		{
			fa[fx]=fy;
			total++;
			answer+=EE[i].dis;
			if(total==tot)
				break;
		}
	}
	printf("%.2lf",answer);
	return 0;
}

　　

151. [USACO Dec07] 建造路径


联系
我们