首页 > 代码库 > HDoj-1875-畅通工程再续-prim算法
HDoj-1875-畅通工程再续-prim算法
畅通工程再续
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 15 Accepted Submission(s) : 6
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
相信大家都听说一个“百岛湖”的地方吧,百岛湖的居民生活在不同的小岛中,当他们想去其他的
小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖,发展首先要解决的问题当然是交通
问题,政府决定实现百岛湖的全畅通!经过考察小组RPRush对百岛湖的情况充分了解后,决定在符
合条件的小岛间建上桥,所谓符合条件,就是2个小岛之间的距离不能小于10米,也不能大于1000米。
当然,为了节省资金,只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。
Input
输入包括多组数据。输入首先包括一个整数T(T <= 200),代表有T组数据。
每组数据首先是一个整数C(C <= 100),代表小岛的个数,接下来是C组坐标,代表每个小岛的坐标,这些坐标都是 0 <= x, y <= 1000的整数。
Output
每组输入数据输出一行,代表建桥的最小花费,结果保留一位小数。如果无法实现工程以达到全部畅通,输出”oh!”.
Sample Input
2
2
10 10
20 20
3
1 1
2 2
1000 1000
Sample Output
1414.2
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 15 Accepted Submission(s) : 6
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
相信大家都听说一个“百岛湖”的地方吧,百岛湖的居民生活在不同的小岛中,当他们想去其他的
小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖,发展首先要解决的问题当然是交通
问题,政府决定实现百岛湖的全畅通!经过考察小组RPRush对百岛湖的情况充分了解后,决定在符
合条件的小岛间建上桥,所谓符合条件,就是2个小岛之间的距离不能小于10米,也不能大于1000米。
当然,为了节省资金,只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。
Input
输入包括多组数据。输入首先包括一个整数T(T <= 200),代表有T组数据。
每组数据首先是一个整数C(C <= 100),代表小岛的个数,接下来是C组坐标,代表每个小岛的坐标,这些坐标都是 0 <= x, y <= 1000的整数。
Output
每组输入数据输出一行,代表建桥的最小花费,结果保留一位小数。如果无法实现工程以达到全部畅通,输出”oh!”.
Sample Input
2
2
10 10
20 20
3
1 1
2 2
1000 1000
Sample Output
1414.2
oh!
#include<stdio.h> #include<math.h> #include<string.h> #define N 1000000 double map[110][110]; struct qiao { int x,y; }qiao[110]; double between(int i,int j) { return sqrt((double)((qiao[i].y-qiao[j].y)*(qiao[i].y-qiao[j].y)+(qiao[i].x-qiao[j].x)*(qiao[i].x-qiao[j].x))); } double prim(int n) { int used[110]; int i,j,k; double min,sum=0; double dis[110]; memset(used,0,sizeof(used)); memset(dis,0,sizeof(dis)); for(i=1;i<=n;i++) { dis[i]=map[i][1]; } for(i=1;i<n;i++) { min=N; for(j=2;j<=n;j++) { if(min>dis[j] && used[j]==0) { min=dis[j]; k=j; } } if(min==N) return 0; sum+=min; used[k]=1; for(j=1;j<=n;j++) { if(used[j]==0 && dis[j]>map[k][j]) dis[j]=map[k][j]; } } return sum; } int main() { int n,m,i,j; double t,sum; scanf("%d",&m); while(m--) { scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d %d",&qiao[i].x,&qiao[i].y); for(j=1;j<=i;j++) { t=between(i,j); if(t>=10 && t<=1000) map[i][j]=map[j][i]=t; else map[i][j]=map[j][i]=N; } } sum=100*prim(n); if(sum==0) printf("oh!\n"); else printf("%.1lf\n",sum); } return 0; }
HDoj-1875-畅通工程再续-prim算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。