Description
相信大家都听说一个“百岛湖”的地方吧,百岛湖的居民生活在不同的小岛中,当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖,发 展首先要解决的问题当然是交通问题,政府决定实现百岛湖的全畅通!经过考察小组RPRush对百岛湖的情况充分了解后,决定在符合条件的小岛间建上桥,所 谓符合条件,就是2个小岛之间的距离不能小于10米,也不能大于1000米。当然,为了节省资金,只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。
Input
输入包括多组数据。输入首先包括一个整数T(T <= 200),代表有T组数据。
每组数据首先是一个整数C(C <= 100),代表小岛的个数,接下来是C组坐标,代表每个小岛的坐标,这些坐标都是 0 <= x, y <= 1000的整数。
每组数据首先是一个整数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<iostream> #include<string.h> #include<math.h> #include<algorithm> using namespace std; const double inf=999999.9; struct node{ double x,y; }que[200]; double map[150][150]; double dis[150]; int vis[150]; int n; double prim(int u) { double sum=0; for(int i=1; i<=n; i++) { dis[i]=map[u][i]; } vis[u]=1; for(int k=1; k<n; k++) { double tmin=inf; int temp=0; for(int j=1; j<=n; j++) { if(dis[j]<tmin&&!vis[j]) { tmin=dis[j]; temp=j; } } if(temp==0){ return -1; } vis[temp]=1; sum+=tmin; for(int i=1; i<=n; i++) { if(dis[i]>map[temp][i]&&!vis[i]) dis[i]=map[temp][i]; } } return sum; } double dist(int a,int b){ return sqrt((que[a].x-que[b].x)*(que[a].x-que[b].x)+(que[a].y-que[b].y)*(que[a].y-que[b].y)); } int main() { int t; scanf("%d",&t); while(t--) { int m; memset(vis,0,sizeof(vis)); memset(dis,0,sizeof(dis)); scanf("%d",&m); for(int i=1;i<=m;i++){ scanf("%lf%lf",&que[i].x,&que[i].y); } n=m; for(int i=1; i<=n; i++) { for(int j=1; j<=n; j++) { double tmp=dist(i,j); if(i==j) map[i][j]=0; else if(tmp<10||tmp>1000) map[i][j]=inf; else map[i][j]=tmp; } } double ans=prim(1); if(ans==-1) printf("oh! "); else printf("%.1lf ",ans*100); } return 0; }