畅通工程再续

畅通工程再续

畅通工程再续

from hdu 1875

Time limit：1s

Memory limit：32MB

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

2210 1020 2031 12 21000 1000

Sample Output

1414.2oh!

O(n^2)遍历点，然后满足10 – 1000就建立一条边压入到vector，然后就是普通最小生成树的问题了

#include#include#include#includeusing namespace std;struct point{ int x,y;}po[105]; //点struct E{ int f,t; double w;}e; //边bool cmp(E a,E b){ //比较规则，按边权从小到大 return a.w < b.w;}vector v;int T,c,need; //测试组数,点，需要的边（c - 1）int father[105];int find(int x){ if(father[x] == x) return x; return father[x] = find(father[x]);}void init(){ //各种数据得初始化 scanf("%d",&c); v.clear(); for(int i = 1;i <= c;++i) scanf("%d %d",&po[i].x,&po[i].y); for(int i = 1;i < c;++i) for(int j = i + 1;j <= c;++j){ double l = sqrt(pow(po[i].x - po[j].x,2) + pow(po[i].y - po[j].y,2)); if(l >= 10 && l <= 1000) e.f = i,e.t = j,e.w = l,v.push_back(e); } sort(v.begin(),v.end(),cmp); for(int i = 1;i <= c;++i) father[i] = i; need = c - 1;}int main(){ scanf("%d",&T); while(T--){ init(); double sum = 0; for(int i = 0,j = v.size();i < j;++i){ int x = find(v[i].f),y = find(v[i].t); if(x != y) father[x] = y,sum += v[i].w,--need; } if(need) printf("oh!\n"); else printf("%.1lf\n",sum * 100); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。