Qin Shi Huang's National Road System HDU - 4081 次小生成树之secondprim算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Qin Shi Huang's National Road System HDU - 4081 次小生成树之secondprim算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含5890字,纯文字阅读大概需要9分钟。
内容图文
Qin Shi Huang undertook gigantic projects, including the first version of the Great Wall of China, the now famous city-sized mausoleum guarded by a life-sized Terracotta Army, and a massive national road system. There is a story about the road system:
There were n cities in China and Qin Shi Huang wanted them all be connected by n-1 roads, in order that he could go to every city from the capital city Xianyang.
Although Qin Shi Huang was a tyrant, he wanted the total length of all roads to be minimum,so that the road system may not cost too many people‘s life. A daoshi (some kind of monk) named Xu Fu told Qin Shi Huang that he could build a road by magic and that magic road would cost no money and no labor. But Xu Fu could only build ONE magic road for Qin Shi Huang. So Qin Shi Huang had to decide where to build the magic road. Qin Shi Huang wanted the total length of all none magic roads to be as small as possible, but Xu Fu wanted the magic road to benefit as many people as possible ---- So Qin Shi Huang decided that the value of A/B (the ratio of A to B) must be the maximum, which A is the total population of the two cites connected by the magic road, and B is the total length of none magic roads.
Would you help Qin Shi Huang?
A city can be considered as a point, and a road can be considered as a line segment connecting two points.
InputThe first line contains an integer t meaning that there are t test cases(t <= 10).
For each test case:
The first line is an integer n meaning that there are n cities(2 < n <= 1000).
Then n lines follow. Each line contains three integers X, Y and P ( 0 <= X, Y <= 1000, 0 < P < 100000). (X, Y) is the coordinate of a city and P is the population of that city.
It is guaranteed that each city has a distinct location.OutputFor each test case, print a line indicating the above mentioned maximum ratio A/B. The result should be rounded to 2 digits after decimal point.Sample Input
2 4 1 1 20 1 2 30 200 2 80 200 1 100 3 1 1 20 1 2 30 2 2 40
Sample Output
65.00 70.00
题意:有n个村庄,现在要在这些村庄之间修建道路,保证所有村庄都能相互连通,修建道路的花费等于道路的长度,现在你有一个神奇的宝贝。它能够帮你修建一条无限长的到路并且没有任何花费。你肯定非把这个宝贝花在最长道路上,
但是现在要求这个宝贝要用在A/B的值最大的道路上,其中A表示道路两头村庄的人数和,B表示你除了这个道路以外你修建的其他道路的花费和。输入为每个村庄的坐标以及这个村庄的人数,有多组输入样例,对于每个样例你都要输出
最大的A/B的值,并且结果保留两位小数。
思路:要保证A/B最大,首先要保证B最小,因此可以得出第一步是先求出所有村庄连通的道路的花费的最小值,也就是最小生成树,然后看你的那个宝贝用在哪条道路,则有非用到次小生成树算法,最后求出结果即可
最小生成树算法个人总结:https://www.cnblogs.com/mzchuan/p/11720280.html
次小生成树算法个人总结:https://www.cnblogs.com/mzchuan/p/11828010.html
代码:
1 #include <cstdio> 2 #include <fstream> 3 #include <algorithm> 4 #include <cmath> 5 #include <deque> 6 #include <vector> 7 #include <queue> 8 #include <string> 9 #include <cstring> 10 #include <map> 11 #include <stack> 12 #include <set> 13 #include <sstream> 14 #include <iostream> 15#define mod 998244353 16#define eps 1e-6 17#define ll long long 18#define INF 0x3f3f3f3f 19usingnamespace std; 20 21//ma存放两点之间的初始距离 22double ma[1000][1000]; 23//low存放到起点的最小距离, 24double low[1000]; 25//per存放与当前点连接距离最短的另一个点 26int per[1000]; 27//bj用于判断该点时候在生成树中,con用于标记在生成树中的边 28bool bj[1000],con[1000][1000]; 29//maxn存放两点之间的最大值 30double maxn[1000][1000]; 31int n; 32//点的坐标以及人数 33struct node 34{ 35double x,y; 36double s; 37}; 38 node no[1000]; 39//计算两点之间的距离 40double dis(node a,node b) 41{ 42return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 43} 44//最小生成树算法,u表示树的起点 45double secondprim(int u) 46{ 47for(int i=0;i<n;i++) 48 { //初始low的距离与per指向的点 49 low[i]=ma[u][i]; 50 per[i]=u; 51 } 52//初始化标记 53 memset(bj,0,sizeof(bj)); 54 memset(con,0,sizeof(con)); 55//起点是树上的第一个点,标记 56 bj[u]=1; 57//ans保存树的所有权值和 58double ans=0; 59//遍历其他n-个点 60for(int i=0;i<n-1;i++) 61 { 62//通过遍历找到距离当前起点的最短的边 63double mi=INF; 64int v=-1; 65for(int j=0;j<n;j++) 66 { 67if(!bj[j]&&low[j]<mi) 68 { 69 v=j; 70 mi=low[j]; 71 } 72 } 73//有最短边后 74if(v!=-1) 75 { 76//将这个边的两个点标记 77 con[v][per[v]]=con[per[v]][v]=1; 78//累加权值 79 ans+=mi; 80//标记这个点 81 bj[v]=1; 82//记录这个边的值, 83 maxn[per[v]][v]=maxn[v][per[v]]=mi; 84//再遍历一遍,以更新数据 85for(int j=0;j<n;j++) 86 { 87//j表示的点再树上,且j不是终点 88if(bj[j]&&j!=v) 89 { //更新v与其他在树上的点之间的最大权值 90 maxn[j][v]=maxn[v][j]=max(maxn[j][per[v]],maxn[per[v]][v]); 91 } 92//j表示的点不在树上,且满足更新需要 93if(!bj[j]&&low[j]>ma[v][j]) 94 { 95//更新low的距离和per指向的点 96 low[j]=ma[v][j]; 97 per[j]=v; 98 } 99 } 100 } 101 } 102//非严格次小生成树103double ansed=0; 104//遍历所有点与其他点 105//求最小的A/B,A表示这个边两头的人数和,106for(int i=0;i<n-1;i++) 107 { 108for(int j=i+1;j<n;j++) 109 { 110//如果这两个点不在树上111if(!con[i][j]) 112 { 113//B表示s 删除 加上一个权值后形成的闭环的最大权值114 ansed=max(ansed,(no[i].s+no[j].s)/(ans-maxn[i][j])); 115 }//如果者两个点在树上116else117 { 118 ansed=max(ansed,(no[i].s+no[j].s)/(ans-ma[i][j])); 119 } 120 } 121 } 122return ansed; 123} 124int main() 125{ 126int t; 127 scanf("%d",&t); 128while(t--) 129 { 130 scanf("%d",&n); 131for(int i=0;i<n;i++) 132 { 133 scanf("%lf %lf %lf",&no[i].x,&no[i].y,&no[i].s); 134 } 135//将点的坐标转换成点的距离信息136for(int i=0;i<n;i++) 137 { 138for(int j=i;j<n;j++) 139 { 140 ma[j][i]=ma[i][j]=dis(no[i],no[j]); 141 } 142 } 143 printf("%0.2lf\n",secondprim(0)); 144 } 145 }
原文:https://www.cnblogs.com/mzchuan/p/11828013.html
内容总结
以上是互联网集市为您收集整理的Qin Shi Huang's National Road System HDU - 4081 次小生成树之secondprim算法全部内容,希望文章能够帮你解决Qin Shi Huang's National Road System HDU - 4081 次小生成树之secondprim算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。