Input
相信大家都听说一个 "百岛湖" 的地方吧。百岛湖的居民生活在不同的小岛中。当他们想去其它的小岛时都要通过划小船来实现。如今政府决定大力发展百岛湖。发展首先要解决的问题当然是交通问题,政府决定实现百岛湖的全畅通!经过考察小组 RPRush 对百岛湖的情况充分了解后,决定在符合条件的小岛间建上桥,所谓符合条件,就是 2 个小岛之间的距离不能小于 10 米。也不能大于 1000 米。当然,为了节省资金,仅仅要求实现随意 2 个小岛之间有路通就可以。当中桥的价格为 100 元 / 米。
Problem Description
输入包含多组数据。输入首先包含一个整数 T(T <= 200),代表有 T 组数据。每组数据首先是一个整数 C(C <= 100), 代表小岛的个数,接下来是 C 组坐标,代表每一个小岛的坐标,这些坐标都是 0 <= x, y <= 1000 的整数。Output
每组输入数据输出一行,代表建桥的最小花费,结果保留一位小数。假设无法实现 project 以达到所有畅通,输出 "oh!".
Sample Input
- 2
- 2
- 10 10
- 20 20
- 3
- 1 1
- 2 2
- 1000 1000
Sample Output
- 1414.2
- oh!
//Kruscal
- #include<cstdio>
- #include<algorithm>
- #include<cmath>
- using namespace std;
- struct Island
- {
- int x,y;
- };
- struct node
- {
- int u,v;
- double w;
- };
- Island arr[220];
- node edge[20000];
- int per[220];
- int n;
- bool cmp(node a,node b)
- {
- return a.w<b.w;
- }
- void init()
- {
- for(int i=1;i<=n;++i)
- {
- per[i]=i;
- }
- }
- int find(int x)
- {
- if(x==per[x]) return x;
- return per[x]=find(per[x]);
- }
- bool join(int x,int y)
- {
- int fx=find(x);
- int fy=find(y);
- if(fx!=fy)
- {
- per[fx]=fy;
- return 1;
- }
- return 0;
- }
- int main()
- {
- int T;
- int i,j,k;
- double x,y;
- scanf("%d",&T);
- while(T--)
- {
- scanf("%d",&n);
- init();
- for(i=1;i<=n;++i)
- {
- scanf("%d%d",&arr[i].x,&arr[i].y);
- }
- //m=n*(n-1)/2;
- k=0;
- for(i=1;i<=n;++i)//把全部路记录在node结构体中
- {
- for(j=i+1;j<=n;++j)
- {
- edge[k].u=i;
- edge[k].v=j;
- x=(arr[j].y-arr[i].y)*(arr[j].y-arr[i].y);
- y=(arr[j].x-arr[i].x)*(arr[j].x-arr[i].x);
- double temp=sqrt(x+y);
- edge[k++].w=temp;
- }
- }
- sort(edge,edge+k,cmp);
- double sum=0;
- for(i=0;i<k;++i)
- {
- if(edge[i].w<=1000&&edge[i].w>=10&&join(edge[i].u,edge[i].v))//假设两个岛的距离不符合要求就会把join(edge[i].u,edge[i].v)短路
- {
- sum+=edge[i].w;
- }
- }
- int cnt=0;
- bool flag=0;
- for(i=1;i<=n;++i)//短路了就不会运行了,也就不会连接了,就仅仅须要推断根节点的个数
- {
- if(i==per[i]) cnt++;
- if(cnt>1) //不等于1就还有元素(小岛)没连起来,不满足题意
- {
- flag=1;
- break;
- }
- }
- if(flag) printf("oh!\n");
- else
- printf("%.1lf\n",sum*100);
- }
- return 0;
- }
//Prim
- #include <stdio.h>
- #include <string.h>
- #include <math.h>
- #define N 110
- #define INF 0x3f3f3f3f
- int n;
- int i,j;
- double map[N][N];
- bool vis[N];//标记是否已经放入最小生成树的那个集合里了
- double low[N];//记录不在已经增加最小生成树的这个集合里的元素到这个 集合的最小距离
- int x[N],y[N];
- double dis(int i,int j)
- {
- return sqrt(1.0*(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
- }
- void input()
- {
- for(i=1;i<=n;++i)
- scanf("%d%d",&x[i],&y[i]);
- for(i=1;i<=n;++i)
- for(j=1;j<=n;++j)
- {
- map[i][j]=dis(i,j);
- if(map[i][j]>1000||map[i][j]<10)
- {
- map[i][j]=INF;
- }
- }
- }
- void prim()
- {
- double sum=0;
- memset(vis,0,sizeof(vis));
- int pos=1;//从1開始
- for(i=1;i<=n;++i)//第一次给low赋值
- {
- low[i]=map[1][i];
- }
- vis[1]=1;
- //已经找到一个点1。再找n-1个
- for(i=1;i<n;++i)
- {
- double min=INF;
- for(j=1;j<=n;++j)
- {
- if(!vis[j]&&min>low[j])//找下一个点到这个集合的最小值
- {
- min=low[j];//记下这个最小值
- pos=j;//记下这个点
- }
- }
- if(min==INF)
- {
- printf("oh!\n");
- return ;
- }
- sum+=min;
- vis[pos]=1;//把刚刚找到的这个点增加集合
- for(j=1;j<=n;++j) //更新low数组
- {
- if(!vis[j]&&low[j]>map[pos][j])
- {
- low[j]=map[pos][j];
- }
- }
- }
- printf("%.1lf\n",sum*100);
- }
- int main()
- {
- int T;
- scanf("%d",&T);
- while(T--)
- {
- scanf("%d",&n);
- input();
- prim();
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2048761.html