题目大意:秦始皇要在n个城市之间修筑一条道路使得任意两个城市均可连通。有个道士可以用法力帮忙修一条路。秦始皇希望其他的道路总长B最短且用法术连接的两个城市的人口之和A尽量大,因此下令寻找一个A / B的最大方案。(转自http://blog.csdn.net/murmured/article/details/18865721,侵删)

题解:考虑修哪一条路,此时A确定,断掉这条路后,形成两个连通块,不难发现两个连通块都应是MST才能让B最短。此时B为两个连通块的MST权值和
这个过程相当于选了一条路u->v后,在整张图的MST上,把MST上u->v路径上最大边删掉。

其实不用枚举边,枚举u和v即可

空间开小了,RE了无数发。。。

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <string>
#include <cmath>
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define abs(a) ((a) < 0 ? (-1 * (a)) : (a))
template<class T>
inline void swap(T &a, T &b)
{
T tmp = a;a = b;b = tmp;
}
inline void read(int &x)
{
x = ;char ch = getchar(), c = ch;
while(ch < '' || ch > '') c = ch, ch = getchar();
while(ch <= '' && ch >= '') x = x * + ch - '', ch = getchar();
if(c == '-') x = -x;
} const int INF = 0x3f3f3f3f;
const int MAXN = + ;
const int MAXM = + ; int x[MAXM], y[MAXM], node[MAXM], n, m, t, u[MAXM], v[MAXM], cnt[MAXM], fa[MAXM], vis[MAXN];
double ma[MAXN][MAXN], w[MAXM];
struct Edge
{
int u,v,nxt;
double w;
Edge(int _u, int _v, double _w, int _nxt){u = _u;v = _v;w = _w;nxt = _nxt;}
Edge(){}
}edge[MAXM << ];
int head[MAXN], cntt;
inline void insert(int a, int b, double c)
{
edge[++cntt] = Edge(a,b,c,head[a]);
head[a] = cntt;
}
int find(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);}
int cmp(int x, int y){return w[x] < w[y];} int tiaoshi;
void dfs(int x, int pre)
{
vis[x] = ;
for(int pos = head[x];pos;pos = edge[pos].nxt)
{
int v = edge[pos].v;
if(v == pre) continue;
for(int i = ;i <= n;++ i)
if(i == v || !vis[i]) continue;
else ma[i][v] =ma[v][i] = max(ma[i][v], max(ma[v][i], max(ma[x][i], max(ma[i][x], edge[pos].w))));
dfs(v, x);
}
}
int main()
{
read(t);
for(;t;--t)
{
tiaoshi = ;
read(n);memset(ma, , sizeof(ma)), memset(vis, , sizeof(vis)), memset(head, , sizeof(head)), cntt = , m = ;
for(int i = ;i <= n;++ i) read(x[i]), read(y[i]), read(node[i]);
for(int i = ;i <= n;++ i)
for(int j = i + ;j <= n;++ j)
++ m, u[m] = i, v[m] = j, w[m] = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])), cnt[m] = m, fa[m] = m;
std::sort(cnt + , cnt + + m, cmp);
int tmp = ;
double ans = ;
double ans2 = ;
for(int i = ;i <= m;++ i)
{
int f1 = find(u[cnt[i]]), f2 = find(v[cnt[i]]);
if(f1 == f2) continue;
fa[f1] = f2;
insert(u[cnt[i]], v[cnt[i]], w[cnt[i]]), insert(v[cnt[i]], u[cnt[i]], w[cnt[i]]);
ans += w[cnt[i]];
++ tmp;if(tmp == n - ) break;
}
dfs(, -);
for(int i = ;i <= n;++ i)
for(int j = i + ;j <= n;++j)
{
if(ans == ma[i][j]) continue;
ans2 = max(ans2, (double)(node[i] + node[j]) / (ans - ma[i][j]));
}
printf("%.2lf\n", ans2);
}
return ;
}

LA5713

最新文章

  1. Android okHttp网络请求之缓存控制Cache-Control
  2. ob_start()
  3. P1195 口袋的天空
  4. umask setuid setgid
  5. 【服务器防护】WEB防护 - WEBSHELL攻击探测【转载】
  6. Linux常用配置文件解析
  7. 详解 Objective-C 中的 Runtime
  8. CoreText实现图文混排之点击事件-b
  9. MySQL驱动阅读------executeQuery查询的过程,基于JDBC-----5.1.26
  10. Spring boot Mybatis
  11. VMware 虚拟机的网络连接方式详解
  12. vs2013下载地址以及安装方法
  13. javaAPI中的常用 类 以及接口
  14. Struct_2路径问题
  15. MVCC(Multi-version Cocurrent Control)多版本并发控制协议
  16. Python中的@符号
  17. c++ 异常处理(1)
  18. tidb在DDL语句方面的测试
  19. Python list 常用方法总结
  20. Kubernetes DNS 高阶指南(转发别人 解析很详细)

热门文章

  1. &lt;随便写&gt;进程基本知识
  2. READING | 我是一只IT小小鸟
  3. curl http_code 状态码
  4. 获取m,n之间的随机整数
  5. leetcode-119-杨辉三角②
  6. 【JZOJ3303】城市规划
  7. 0901NOIP模拟测试赛后总结
  8. 微信公众号 SVG长按互动
  9. webstorm中使用git管理服务器上的代码——入门级
  10. iOS开发CoreData的简单使用