[Usaco2007 Dec]Building Roads 修建道路[最小生成树]

时间：2021-09-07 18:27:14

Description

Farmer John最近得到了一些新的农场，他想新修一些道路使得他的所有农场可以经过原有的或是新修的道路互达（也就是说，从任一个农场都可以经过一些首尾相连道路到达剩下的所有农场）。有些农场之间原本就有道路相连。 所有N(1 <= N <= 1,000)个农场（用1..N顺次编号）在地图上都表示为坐标为(X_i, Y_i)的点(0 <= X_i <= 1,000,000；0 <= Y_i <= 1,000,000)，两个农场间道路的长度自然就是代表它们的点之间的距离。现在Farmer John也告诉了你农场间原有的M(1 <= M <= 1,000)条路分别连接了哪两个农场，他希望你计算一下，为了使得所有农场连通，他所需建造道路的最小总长是多少。

Input

* 第1行: 2个用空格隔开的整数：N 和 M

* 第2..N+1行: 第i+1行为2个用空格隔开的整数：X_i、Y_i * 第N+2..N+M+2行: 每行用2个以空格隔开的整数i、j描述了一条已有的道路， 这条道路连接了农场i和农场j

Output

* 第1行: 输出使所有农场连通所需建设道路的最小总长，保留2位小数，不必做 任何额外的取整操作。为了避免精度误差，计算农场间距离及答案时 请使用64位实型变量

Sample Input

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

输入说明:

FJ一共有4个坐标分别为(1,1)，(3,1)，(2,3)，(4,3)的农场。农场1和农场
4之间原本就有道路相连。

Sample Output

4.00

输出说明:

FJ选择在农场1和农场2间建一条长度为2.00的道路，在农场3和农场4间建一
条长度为2.00的道路。这样，所建道路的总长为4.00，并且这是所有方案中道路
总长最小的一种。

本来快写完的题解= = 结果win7更新的时候按到重启了QAQ 没保存...想哭

算了。。再写一份好了

题解：

看到题目中的 使所有点连通并且使总值最小，就应该想到最小生成树，这个应该很容易吧？

我先把任意一个点到除它本身以外的所有点的距离（也就是边权）都求出来，把相连的两个结点之间的边权赋为0

然后就是按照裸的最小生成树写即可；

MARK一下细节：

这题最开始测试的时候WA了三个点，调试一下发现dist的值有的为 -nan0cx00000

问了一下学长，据说是因为除以0或是爆范围才会这种奇怪的值

分别断点之后发现是在求两点之间的距离的时候

double d(int x1,int y1,int x2,int y2){
 return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

(x1-x2)*(x1-x2)就已经爆int了

之后把int 改成了 long long 就愉快的A了

感觉这种爆范围的地方特别要小心，上次CF的某道题mod的时候都会爆int，比较坑....

附上代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

#include <cmath>

#include <string>

using namespace std;

const int maxn=1001;

int n,m;

struct node{

	int x,y;

}a[maxn];

int fa[maxn*maxn];

int x,y;

struct kru{

	int num1,num2;

	double dist;

}f[maxn*maxn];

int tot=0;

double ans=0;

bool cmp(const kru &a,const kru &b){

	return a.dist<b.dist?1:0;

}

double d(long long x1,long long y1,long long  x2,long long y2){

	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));

}

int find(int x){

	if(fa[x]==x) return x; else return fa[x]=find(fa[x]);

}

int main(){

	freopen("roads.in","r",stdin);

	freopen("roads.out","w",stdout);

    //freopen("data.txt","r",stdin);

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++) fa[i]=i;

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

		scanf("%d%d",&a[i].x,&a[i].y);

	}

	for(int i=1;i<=m;i++){

		scanf("%d%d",&x,&y);

		f[++tot].num1=x;

		f[tot].num2=y;

		f[tot].dist=0;

	}

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

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

	   	  f[++tot].num1=i;

	   	  f[tot].num2=j;

	   	  f[tot].dist=d(a[i].x,a[i].y,a[j].x,a[j].y);

	   }

	sort(f+1,f+tot+1,cmp);

	int k=0;

	for(int i=1;i<=tot;i++){

		int u=f[i].num1;

		int v=f[i].num2;

		if(find(u)!=find(v)){

			ans+=f[i].dist;

			fa[find(u)]=find(v);

			k++;

		}

		if(k==n-1) break;

	}

	printf("%.2f",ans);

	return 0;

}

相关文章