HPUOJ---2017寒假训练--专题2/N-畅通工程再续（最小生成树）

2019-11-06 08:23:05

字体：大中小

来源：转载

供稿：网友

N - 畅通工程再续

相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖，发展首先要解决的问题当然是交通问题，政府决定实现百岛湖的全畅通！经过考察小组RPRush对百岛湖的情况充分了解后，决定在符合条件的小岛间建上桥，所谓符合条件，就是2个小岛之间的距离不能小于10米，也不能大于1000米。当然，为了节省资金，只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。Input输入包括多组数据。输入首先包括一个整数T(T <= 200)，代表有T组数据。每组数据首先是一个整数C(C <= 100),代表小岛的个数，接下来是C组坐标，代表每个小岛的坐标，这些坐标都是 0 <= x, y <= 1000的整数。 Output每组输入数据输出一行，代表建桥的最小花费，结果保留一位小数。如果无法实现工程以达到全部畅通，输出”oh!”.Sample Input

2210 1020 2031 12 21000 1000Sample Output1414.2oh!最小生成树:两个代码的区别就在于新结构体的下标，sort排序时很重要。#include<cstdio>#include<algorithm>#include<cmath>using namespace std;struct node{	double x,y; }da[100+11]; struct node2 { 	int u,v; 	double e; }a[5000+111]; bool cmp (node2 A,node2 B) { 	return A.e<B.e ; } int f[100+11]; double dis (node A,node B)              //写一个函数来计算两点距离  { 	double s; 	s=sqrt((A.x -B.x )*(A.x -B.x )+(A.y -B.y )*(A.y -B.y ) ); 	return s; } int find(int x) { 	if(x==f[x]) 	   return x; 	else  	   return (f[x]=find(f[x])); } int join(int x,int y)         //需要连接点，并返回是哪两个点 连在一起  { 	int fx,fy; 	fx=find(x); 	fy=find(y); 	if(fx!=fy) 	{ 	 	f[fx]=fy; 	 	return 1;	}	return 0;//两个点根节点相同，说明已经连好，不需再连，否则会成环 } int main() { 	int T,C,i,j,p; 	scanf("%d",&T); 	while(T--) 	{ 		double sum=0,s; 		scanf("%d",&C); 		for(i=1;i<=C;i++) 			f[i]=i;              //赋初值 		for(i=1;i<=C;i++)		{			scanf("%lf%lf",&da[i].x ,&da[i].y );//最后要输出结果是double,所以输入也要是double 		}		p=-1;		for(i=1;i<=C-1;i++)		{		    for(j=i+1;j<=C;j++)		    {		    	s=dis(da[i],da[j]);		    	if(s>=10&&s<=1000)              //将符合条件的点和权值存入一个新的数组 		    	{		    		p++; 		    		a[p].u =i;		    		a[p].v =j;		    		a[p].e =s;				}			}		}		sort(a,a+p+1,cmp);		int ach=0;		for(i=0;i<=p;i++)		{			if(join(a[i].u ,a[i].v ))			{				sum+=a[i].e;				ach++;			}		}		sum*=100.0;		if(ach==C-1)           //C个点，不成环连接全部连好需要C-1条路 		    printf("%.1lf/n",sum);		else		    printf("oh!/n");	}	 return 0; }#include<cstdio>#include<algorithm>#include<cmath>using namespace std;struct node{	double x,y; }da[100+11]; struct node2 { 	int u,v; 	double e; }a[5000+111]; bool cmp (node2 A,node2 B) { 	return A.e<B.e ; } int f[100+11]; double dis (node A,node B) { 	double s; 	s=sqrt((A.x -B.x )*(A.x -B.x )+(A.y -B.y )*(A.y -B.y ) ); 	return s; } int find(int x) { 	if(x==f[x]) 	   return x; 	else  	   return (f[x]=find(f[x])); } int join(int x,int y) { 	int fx,fy; 	fx=find(x); 	fy=find(y); 	if(fx!=fy) 	{ 	 	f[fx]=fy; 	 	return 1;	}	return 0;} int main() { 	int T,C,i,j,p; 	scanf("%d",&T); 	while(T--) 	{ 		double sum=0,s; 		scanf("%d",&C); 		for(i=1;i<=C;i++) 		{ 			f[i]=i;		}		for(i=1;i<=C;i++)		{			scanf("%lf%lf",&da[i].x ,&da[i].y );		}		p=0;            //与另一个代码的区别就在p 		for(i=1;i<=C-1;i++)		{		    for(j=i+1;j<=C;j++)		    {		    	s=dis(da[i],da[j]);		    	if(s>=10&&s<=1000)		    	{		    				    		a[p].u =i;		    		a[p].v =j;		    		a[p].e =s;		    		p++;				}			}		}		sort(a,a+p,cmp);//第一个参数表示排序的首地址，第二个末地址，第三个排序方法 		int ach=0;		for(i=0;i<p;i++)		{			if(join(a[i].u ,a[i].v ))//原来没有连在一起的，需要连在一起，加上权值，原来已经连好了的，就不用再加了 			{				sum+=a[i].e;				ach++;			}		}		sum*=100.0;		if(ach==C-1)		    printf("%.1lf/n",sum);		else		    printf("oh!/n");	}	 return 0; }

上一篇：C#通用类库--汉字转拼音

下一篇：C#通用类库--农历类（很全面）