https://vjudge.net/problem/UVALive-5713

题意:

秦朝有n个城市,需要修建一些道路使得任意两个城市之间都可以连通。道士徐福声称他可以用法术修路,不花钱,也不用劳动力,但只能修一条路,因此需要慎重选择用法术修哪一条路。秦始皇不仅希望其他道路的总长度B尽量短(这样可以节省劳动力),还希望法术连接的两个城市的人口之和A尽量大,因此下令寻找一个使得A/B最大的方案。你的任务是找到这个方案。

任意两个城市之间都可以修路,长度为两个城市之间的欧几里德距离。

思路:

先计算出最小生成树,之后用法术修的路肯定在最小生成树当中,那么之后我们就可以枚举边u-v。

当然,需要预处理,像最小生成树一样,计算出u和v之间唯一路径上的最大权maxcost[u][v]。

 #include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
typedef long long LL;
const int maxn=+; struct node
{
int u,v;
double dist;
bool operator < (const node& rhs) const
{
return dist<rhs.dist;
}
}edge[maxn*maxn]; int n;
int cnt;
int p[maxn];
int x[maxn],y[maxn];
int num[maxn];
vector<int> g[maxn]; //存储最小生成树中结点u的邻接结点
vector<double> c[maxn]; //c[u][i]表示结点u和和结点g[u][i]之间的边权 double maxcost[maxn][maxn]; //u,v两点之间的最大边权
vector<int> nodes; int find(int x)
{
return x==p[x]?x:p[x]=find(p[x]);
} double MST()
{
sort(edge,edge+cnt);
int tot_edge=;
double tot_q=;
for(int i=;i<cnt;i++)
{
int x=edge[i].u, y=edge[i].v;
int u=find(x), v=find(y);
if(u!=v)
{
p[u]=v;
g[x].push_back(y); c[x].push_back(edge[i].dist);
g[y].push_back(x); c[y].push_back(edge[i].dist);
tot_q+=edge[i].dist;
if(++tot_edge==n-) break;
}
}
return tot_q;
} void dfs(int u,int fa,double cost) //无根树转有根树,计算出u,v两点之间路径的最大边权
{
for(int i=;i<nodes.size();i++)
{
int x=nodes[i];
maxcost[x][u]=maxcost[u][x]=max(maxcost[x][fa],cost); //更新之前的结点与新加入的结点之前的最大边权
}
nodes.push_back(u);
for(int i=;i<g[u].size();i++)
{
int v=g[u][i];
if(v!=fa) dfs(v,u,c[u][i]);
}
} int main()
{
//freopen("D:\\input.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
cnt=;
scanf("%d",&n);
for(int i=;i<n;i++) {p[i]=i; g[i].clear(); c[i].clear();}
for(int i=;i<n;i++)
{
scanf("%d%d%d",&x[i],&y[i],&num[i]);
for(int j=;j<i;j++)
{
edge[cnt].u=j;
edge[cnt].v=i;
edge[cnt].dist=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
cnt++;
}
}
double tot=MST();
memset(maxcost,,sizeof(maxcost));
nodes.clear();
dfs(,-,);
double ans=-;
for(int i=;i<n;i++)
{
for(int j=i+;j<n;j++)
{
ans=max(ans,(num[i]+num[j])/(tot-maxcost[i][j]));
}
}
printf("%.2lf\n",ans);
}
return ;
}

最新文章

  1. 将DataTable生成树json
  2. iOS的QuickTime Plugin
  3. java常用类 --- Object
  4. 变形--扭曲 skew()
  5. 让TextView出现跑马灯效果
  6. BFC探秘
  7. 化简复杂逻辑,编写紧凑的if条件语句
  8. NYOJ-1070诡异的电梯【Ⅰ】
  9. spring MVC 如何获取session并实现传值到前台
  10. to_date()与to_char()
  11. 二级横向菜单实现——ListView
  12. mycat 使用
  13. lvs,nginx反向代理,虚拟主机
  14. CNN卷积神经网络人脸识别
  15. springboot第一个项目【mybatis】
  16. 深入理解CSS系列(一):理解CSS的盒子模型
  17. 5 -- Hibernate的基本用法 --6 深入Hibernate映射
  18. 配置文件(Machine.config、Web.config、App.config)
  19. oracle 字符处理
  20. MySQL(安装,服务,创建用户及授权)

热门文章

  1. VI乱码, cat 和 more正常
  2. python 递归深度优先搜索与广度优先搜索算法模拟实现
  3. UVA10020:Minimal coverage(最小区间覆盖)
  4. BD面试题1-两个大文件中找出公共记录[转载]
  5. 11g ASM新特性
  6. 关于手机适配中的rem的学习随笔
  7. Jmeter 之下载图片
  8. A class for dynamic icons in Windows
  9. knockout 学习使用笔记----绑定map--双向绑定
  10. XDU 1001 又是苹果(状态压缩)