首页 > 代码库 > HDU 1875 畅通工程再续
HDU 1875 畅通工程再续
畅通工程再续
Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 187564-bit integer IO format: %I64d Java class name: Main
相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖，发展首先要解决的问题当然是交通问题，政府决定实现百岛湖的全畅通！经过考察小组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
2210 1020 2031 12 21000 1000
Sample Output
1414.2oh!
Source
2008浙大研究生复试热身赛（2）——全真模拟
解题：最小生成树。这题比较适合用prim算法做。我处心积虑的用优先队列优化，终于变得更慢了。
这题比较好的体现了prim算法的特点。以前一直不懂prim，后来学了Dijkstra算法后，有点懂prim了，今天这道题目，让我更懂Prim了。
prim求这题的优点是它生成树的过程一直是连通的。一旦发现不合适的边，便oh!
还有预处理，我们是假设加入了1号顶点。故要done[1] = true;
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define pdi pair<double,int>16 #define INF 99999917 using namespace std;18 const int maxn = 110;19 int x[maxn],y[maxn],n;20 double d[maxn],mp[maxn][maxn];21 bool done[maxn];22 priority_queue< pdi,vector< pdi >, greater< pdi > >q;23 double calc(int i,int j){24 double tmp = (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);25 return sqrt(tmp);26 }27 void prim(){28 while(!q.empty()) q.pop();29 for(int i = 1; i <= n; i++){30 d[i] = mp[1][i];31 done[i] = false;32 q.push(make_pair(d[i],i));33 }34 done[1] = true;//注意此处35 double sum = 0;36 bool flag = true;37 while(!q.empty()){38 int u = q.top().second;39 double w = q.top().first;40 q.pop();41 if(done[u]) continue;42 done[u] = true;43 if(w >= INF){flag = false;break;}44 sum += w;45 for(int i = 1; i <= n; i++){46 if(!done[i] && d[i] > mp[u][i]){47 d[i] = mp[u][i];48 q.push(make_pair(d[i],i));49 }50 }51 }52 if(flag) printf("%.1f\n",sum*100);53 else puts("oh!");54 }55 int main() {56 int t,i,j;57 double tmp;58 scanf("%d",&t);59 while(t--){60 scanf("%d",&n);61 for(i = 1; i <= n; i++)62 scanf("%d %d",x+i,y+i);63 for(i = 1; i <= n; i++){64 for(j = 1; j <= n; j++){65 tmp = calc(i,j);66 if(tmp < 10 || tmp > 1000) mp[i][j] = mp[j][i] = INF;67 else mp[i][j] = mp[j][i] = tmp;68 }69 }70 prim();71 }72 return 0;73 }
HDU 1875 畅通工程再续
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。