首页 > ACM题库 > HDU-杭电 > HDU 1875 畅通工程再续-最小生成树-[解题报告] C++
2013
12-23

HDU 1875 畅通工程再续-最小生成树-[解题报告] C++

畅通工程再续

问题描述 :

相信大家都听说一个“百岛湖”的地方吧,百岛湖的居民生活在不同的小岛中,当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖,发展首先要解决的问题当然是交通问题,政府决定实现百岛湖的全畅通!经过考察小组RPRush对百岛湖的情况充分了解后,决定在符合条件的小岛间建上桥,所谓符合条件,就是2个小岛之间的距离不能小于10米,也不能大于1000米。当然,为了节省资金,只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。

输入:

输入包括多组数据。输入首先包括一个整数T(T <= 200),代表有T组数据。
每组数据首先是一个整数C(C <= 100),代表小岛的个数,接下来是C组坐标,代表每个小岛的坐标,这些坐标都是 0 <= x, y <= 1000的整数。

输出:

每组输入数据输出一行,代表建桥的最小花费,结果保留一位小数。如果无法实现工程以达到全部畅通,输出”oh!”.

样例输入:

2
2
10 10
20 20
3
1 1
2 2
1000 1000

样例输出:

1414.2
oh!

与之前的畅通工程类似,求最小生成树,只是要剔除不符合条件的边,还要判断是否是连通图(这个磨蹭了很长时间,只要判断加入集合的点数与题目给出的点数是否相等即可)。

 

#include<iostream>
#include<math.h>
#include<algorithm>
#define NUM 103
using namespace std;
struct point
{
	int x;
	int y;
}pos[NUM];
struct dist
{
	int start;
	int end;
	double val;
}dis[NUM * NUM];

int cmp(const dist &a,const dist &b)
{
	return a.val < b.val;
}

double findDistance(struct point a, struct point b)
{
	return sqrt((double)(a.x-b.x)*(a.x-b.x)+(double)(a.y-b.y)*(a.y-b.y));
}
int set[NUM];
int vex;
void init()  
{  
    for(int i=0;i<=NUM;i++){  
        set[i]=i;  
    }  
 
}  

int find(int x)  
{  
    int r=x;  
    while(r!=set[r])  
        r=set[r];  
    return r;  
}  

void merge(int a, int b)  
{  
    int x=find(a);  
    int y=find(b);  
    if(x!=y){
		set[y]=x;
		vex++;//这里是新增的,用于后面判断加入集合的点数与题目给出的点数是否相等
	}  
          
}  

int isValid(double x)
{
	if(x>=10&&x<=1000)
		return 1;
	else return 0;
}

int main()
{
	int t,c,i,j,index,flag;
	double sum;
	//freopen("C:\\Documents and Settings\\Administrator\\桌面\\input.txt","r",stdin);
	cin>>t;
	while(t--){
		sum=0.0;
		flag=0;
		init();
		cin>>c;
		for(i=0;i<c;i++){
			cin>>pos[i].x>>pos[i].y;
		}
		if(c==1){
			printf("0.0\n");
			continue;
		}
		index=0;//有效的点数
		vex=1;//加入集合中的点数
		for(i=0;i<c;i++)
			for(j=i+1;j<c;j++){
				double mi = findDistance(pos[i],pos[j]);
				if(isValid(mi)){
					dis[index].start=i;
					dis[index].end=j;
					dis[index++].val=mi;
				}
				
			}
		
		sort(dis,dis+index,cmp);
		for(i=0;i<index;i++){
			if(find(dis[i].start)!=find(dis[i].end)&&isValid(dis[i].val)){
				merge(dis[i].start,dis[i].end);
				sum+=dis[i].val;
			}
		}
		if(vex<c)//判断是否连通图
			printf("oh!\n");
		else printf("%.1lf\n",sum*100);

	}
	return 0;
}

 

 

 

解题报告转自:http://blog.csdn.net/jjike/article/details/8581747


  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n