HDU 4081 Qin Shi Huang's National Road System 次小生成树

给你n个城市 每个城市有一定数量的人 连接2个城市需要的花费是他们之间的距离 现在要建一颗最小生成树 可以免费建其中一条边 设A为免费的那条边连接的2个城市的人口之和 B为修建的最小生成树的花费 求最大的A/B

先求最小生成树 设总花费为totol 然后可以枚举免费的那条边 枚举边等于A确定 在这条在最小生成树里的情况下 求最小的B

如果这条边是最小生成树里的边 那么很容易求得B 拿totol减去这条边就行了

如果不是 那么把这条边加到最小生成树 会出现一个环 找到这个环最大的那条边剪掉 就是次小生成树的做法 然后类似求A/B

n^2预处理任意2点之间唯一路径上的最大边权

#include #include #include #include #include using namespace std; const int maxn = 1010; struct poit { double x, y, p; }p[maxn]; struct edge { double dis; int u, v, next; bool select; }e[maxn*maxn], G[maxn*2]; struct node { double dis; int u, v; node(){} node(int u, int v, double d): u(u), v(v), dis(d) {} }; int n; double dp[maxn][maxn], totol; int f[maxn]; int first[maxn], cnt; void AddEdge(int u, int v, double w) { G[cnt].u = u; G[cnt].v = v; G[cnt].dis = w; G[cnt].next = first[u]; first[u] = cnt++; G[cnt].u = v; G[cnt].v = u; G[cnt].dis = w; G[cnt].next = first[v]; first[v] = cnt++; } void init() { for(int i = 1; i Q; Q.push(node(-1, x, 0)); while(!Q.empty()) { node u = Q.front(); Q.pop(); for(int i = first[u.v]; i != -1; i = G[i].next) { if(G[i].v == u.u) continue; double temp = max(u.dis, G[i].dis); dp[x][G[i].v] = max(dp[x][G[i].v], temp); Q.push(node(u.v, G[i].v, temp)); } } } int main() { int T; scanf("%d", &T); while(T--) { scanf("%d", &n); init(); for(int i = 1; i

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:AsyncSocket中tag参数的用处
下一篇:poj1837--Balance(dp:天平问题)
相关文章

poj1258 最小生成树 普林姆

poj2421 最小生成树 克鲁斯

437D(The Child and Zoo)最小生成树

最小生成树

poj 3026 Borg Maze (bfs + 最小

poj 1679 The Unique MST (次小生

ZOJ 1586(最小生成树)

POJ 3026 bfs+最小生成树

poj3026Borg Maze(bfs预处理+最小生

HDU 4786 Fibonacci Tree 最小生成

图文推荐

HDU 4081 Qin Shi Huang's National Road System 次小生成树
ZOJ 3640 Help Me
HDU 4081 Qin Shi Huang's National Road System 次小生成树
CF 518C(Anya and
HDU 4081 Qin Shi Huang's National Road System 次小生成树
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2015-03-07 人气:2
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.040 (s). 10 q(s)