hdu 4081 Qin Shi Huang's National Road System (次小生成树)

Qin Shi Huang's National Road System

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3843    Accepted Submission(s): 1336

Problem Description

During the Warring States Period of ancient China(476 BC to 221 BC), there were seven kingdoms in China ---- they were Qi, Chu, Yan, Han, Zhao, Wei and Qin. Ying Zheng was the king of the kingdom Qin. Through 9 years of wars, he finally conquered all six other kingdoms and became the first emperor of a unified China in 221 BC. That was Qin dynasty ---- the first imperial dynasty of China(not to be confused with the Qing Dynasty, the last dynasty of China). So Ying Zheng named himself "Qin Shi Huang" because "Shi Huang" means "the first emperor" in Chinese.

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.

Input

The 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.

Output

For 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

Source

2011 Asia Beijing Regional Contest

代码:

       n个城市,求解max{ A/b } b为次小生成树!  

  1 //#define LOCAL
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<iostream>
  7 #include<algorithm>
  8 using namespace std;
  9 const int maxn=1005;
 10 const int inf=0x3f3f3f3f;
 11 struct node
 12 {
 13  int x,y,p;
 14  double dist(const node &cc){
 15    return sqrt((double)(x-cc.x)*(x-cc.x)+(y-cc.y)*(y-cc.y));
 16  }
 17 }sac[maxn];
 18 
 19 bool vis[maxn];
 20 bool road[maxn][maxn];
 21 int pre[maxn];
 22 double maxc[maxn][maxn];
 23 double lowcost[maxn];
 24 double map[maxn][maxn];
 25 double res;
 26 void prim(int st,int en){
 27 
 28   memset(vis,0,sizeof(vis));
 29   memset(road,0,sizeof(road));
 30   memset(maxc,0,sizeof maxc);
 31   for(int i=0;i<en;i++){
 32        lowcost[i]=map[st][i];
 33      pre[i]=st;;
 34   }
 35   vis[st]=1;
 36   res=0;
 37   for(int i=0;i<en;i++)
 38   {
 39       double larger=inf;
 40       int pp=-1;
 41       for(int j=0;j<en;j++)
 42     {
 43         if(!vis[j]&&larger>lowcost[j])
 44         {
 45             larger=lowcost[j];
 46             pp=j;
 47         }
 48     }
 49     if(-1==pp)continue;
 50       road[pp][pre[pp]]=road[pre[pp]][pp]=1;
 51      res+=lowcost[pp];
 52      vis[pp]=1;
 53     for(int i=0;i<en;i++)
 54     {
 55 
 56         if(!vis[i]&&lowcost[i]>map[pp][i]){
 57             lowcost[i]=map[pp][i];
 58             pre[i]=pp;
 59         }
 60         //求解生成树的最大边
 61          if(vis[i]&&i!=pp){
 62           maxc[i][pp]=maxc[pp][i]=max(maxc[i][pre[pp]],lowcost[pp]);
 63         }
 64     }
 65   }
 66   return ;
 67 }
 68 
 69 int main()
 70 {
 71   #ifdef LOCAL
 72      freopen("test.in","r",stdin);
 73   #endif
 74    int tt,nn;
 75    scanf("%d",&tt);
 76   while(tt--){
 77       scanf("%d",&nn);
 78   //    memset(map,0,sizeof(map));
 79     for(int i=0;i<nn;i++){
 80        scanf("%d%d%d",&sac[i].x,&sac[i].y,&sac[i].p);
 81         map[i][i]=0;
 82        for(int j=i-1;j>=0;--j){
 83          map[i][j]=map[j][i]=sac[i].dist(sac[j]);
 84        }
 85     }
 86     prim(0,nn);
 87     double ans=0.0;
 88    for(int i=0;i<nn;i++){
 89       for(int j=0;j<nn;j++){
 90           if(i!=j)
 91         {
 92             double tol_p=sac[i].p+sac[j].p;
 93            if(road[i][j])
 94                 ans=max(tol_p/(res-map[i][j]),ans);
 95            else
 96                 ans=max(tol_p/(res-maxc[i][j]),ans);
 97         }
 98       }
 99    }
100    printf("%.2lf\n",ans);
101   }
102   return 0;
103 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Petrichor的专栏

Dataset 列表:机器学习研究

In computer vision, face images have been used extensively to develop face recog...

60410
来自专栏计算机视觉与深度学习基础

计算机视觉著名数据集CV Datasets

Detection PASCAL VOC 2009 datasetClassification/Detection Competitions, Segm...

37680
来自专栏CreateAMind

大量完整的强化学习内容

54750
来自专栏专知

ACL 2018 计算语言学协会接受论文列表

45010
来自专栏CreateAMind

How to Train a GAN? Tips and tricks to make GANs work

While research in Generative Adversarial Networks (GANs) continues to improve th...

32340
来自专栏专知

【论文推荐】最新六篇自动问答相关论文—无监督迁移学习、综述、生成式问答、QDEE、可扩展文档理解

31330
来自专栏专知

国际万维网会议WWW 2018论文列表以及会议日程,一睹为快

2018 年 4 月 23 日至 27 日,第 27 届国际万维网会议(26th International World Wide Web Conference...

689110
来自专栏数据结构与算法

BZOJ3170: [Tjoi2013]松鼠聚会(切比雪夫距离转曼哈顿距离)

有N个小松鼠,它们的家用一个点x,y表示,两个点的距离定义为:点(x,y)和它周围的8个点即上下左右四个点和对角的四个点,距离为1。现在N个松鼠要走到一个松鼠家...

13040
来自专栏机器学习算法与Python学习

【代码集合】深度强化学习Pytorch实现集锦

本次分享的是用PyTorch语言编写的深度强化学习算法的高质量实现,这些IPython笔记本的目的主要是帮助练习和理解这些论文;因此,在某些情况下,我将选择可读...

36720
来自专栏专知

【最新】人工智能领域顶会AAAI 2018 Pre-Proceedings 论文列表(附pdf下载链接)

【导读】人工智能领域顶尖学术会议 AAAI 2018,暨第32届 AAAI 大会将于 2 月 2 日 - 2 月 7 日 在新奥尔良举行。AAAI 是由人工智能...

1.4K60

扫码关注云+社区

领取腾讯云代金券