poj2728 Desert King,最优比例生成树

题意:有n个村庄,村庄在不同坐标和海拔,现在要对所有村庄供水,只要两个村庄之间有一条路即可,
建造水管距离为坐标之间的欧几里德距离(好象是叫欧几里德距离吧),费用为海拔之差
现在要求方案使得费用与距离的比值最小
很显然,这个题目是要求一棵最优比率生成树,

0-1分数规划,0-1分数规划是分数规划的一种特殊情况,分数规划适用于求解最优化问题的,对于求最大的对应解,该理论也有效
这是从网上找到的具体的最优比率生成树的方法的讲解
////////////////////
概念
有带权图G, 对于图中每条边e[i], 都有benifit[i](收入)和cost[i](花费), 我们要求的是一棵生成树T, 它使得 ∑(benifit[i]) / ∑(cost[i]), i∈T 最大(或最小).
这显然是一个具有现实意义的问题.
解法之一 0-1分数规划
设x[i]等于1或0, 表示边e[i]是否属于生成树.
则我们所求的比率 r = ∑(benifit[i] * x[i]) / ∑(cost[i] * x[i]), 0≤i 为了使 r 最大, 设计一个子问题---> 让 z = ∑(benifit[i] * x[i]) - l * ∑(cost[i] * x[i]) = ∑(d[i] * x[i]) 最大 (d[i] = benifit[i] - l * cost[i]) , 并记为z(l). 我们可以兴高采烈地把z(l)看做以d为边权的最大生成树的总权值.
然后明确两个性质:
 1. z单调递减
  证明: 因为cost为正数, 所以z随l的减小而增大.
 2. z( max(r) ) = 0
  证明: 若z( max(r) )    若z( max(r) ) >= 0, 根据性质1, 当z = 0 时r最大.
到了这个地步, 七窍全已打通, 喜欢二分的上二分, 喜欢Dinkelbach的就Dinkelbach.

复杂度
时间 O( O(MST) * log max(r) )
空间 O( O(MST) )
/////////////////////////////
关于分数规划的学习我找到了一篇论文,里面有讲分数规划,特别详细
算法合集之《最小割模型在信息学竞赛中的应用》
黑书上说求最小生成树有O(n)的方法,没去找

迭代+prim

#include #include #include #include #include #include #include #include #include #include #include #define for0(a,b) for(a=0;a=b;--i) using namespace std; typedef long long ll; const int maxn = 1000 + 5; const int maxm = 100005; const int INF = 1e9; double x[maxn], y[maxn], z[maxn]; double cost[maxn][maxn], dist[maxn][maxn]; int n; double Dist(int i, int j) { return sqrt( (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) ); } void init() { int i, j; for1(i,n) scanf("%lf%lf%lf", &x[i], &y[i], &z[i]); for1(i,n) foru(j,i+1,n){ dist[i][j] = dist[j][i] = Dist(i, j); cost[i][j] = cost[j][i] = fabs(z[i] - z[j]); } } int vis[maxn], pre[maxn]; double dis[maxn]; double prim(double p) { int i, j; memset(vis, 0, sizeof vis ); vis[1] = 1; foru(i,2,n) { dis[i] = cost[1][i]-dist[1][i]*p; pre[i] = 1; } double Cost = 0, Len = 0; for0(i,n-1){ double Mincost = INF; int k = -1; for1(j,n){ if(!vis[j] && dis[j]tmp){ dis[j] = tmp; pre[j] = k; } } } return Cost / Len; } void solve() { //牛顿迭代 double x0=0, x=0; while(true){ x = prim(x0); if(fabs(x-x0)

点击复制链接 与好友分享!回本站首页

您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:HDU-4407-Sum(容斥原理)
下一篇:Effective C++ 条款 52:写了placement new也要写placement delete
相关文章

[POJ 2728] 最优比例生成树

poj 3621 Sightseeing Cows(最优比

百度地图API,指定比例尺大小

图文推荐
poj2728 Desert King,最优比例生成树
ZOJ 3640 Help Me
poj2728 Desert King,最优比例生成树
CF 518C(Anya and
poj2728 Desert King,最优比例生成树
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2012-12-24 人气:1
本文关键词:
分享到:

相关文章

  • [POJ 2728] 最优比例生成树 2013-04-12

    概念 有带权图G, 对于图中每条边e[i], 都有benifit[i](收入)和cost[i](花费), 我们要求的是一棵生成树T, 它使得 ∑(benifit[i]) / ∑(cost[i]), i∈T 最大(或最小). 解法:0-1分数规划 设x[i]等于1或0, 表示边e[i]是否属于生成树. 则我们所求的比率 r = ∑(benifit[i] * x[i]) / ∑(cost[i] * x[i]), 0≤i 为了使 r 最大, 设计一个子问题---> 让 z = ∑(benifit

  • HDU 3861 The King's Problem(强连通+二分图最小路径覆盖) 2012-10-13

    HDU 3861 The King’s Problem 题目链接 题意:给定一个有向图,求最少划分成几个部分满足下面条件 互相可达的点必须分到一个集合 一个对点(u, v)必须至少有u可达v或者v可达u 一个点只能分到一个集合 思路:先强连通缩点,然后二分图匹配求最小路径覆盖 代码: #include #include #include #include #include using namespace std; const int N = 5005; int t, n, m; vector g

  • hdu3861The King's Problem 2012-12-12

    The King’s Problem Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 1366 Accepted Submission(s): 507 Problem Description In the Kingdom of Silence, the king has a new problem. There are N cities in

  • 流星蝴蝶剑9.07中的霸王:匕首.魔术师:忍刀.KING:指虎 2013-01-06

    9.07的KING:指虎 玩了这么多年,我始终认为虎才是907武器之王 虎强大的原因体现在哪? 其一:破防频率高 破防快并不是他的立足点,你说前前A和左右A,哪个有匕首后前A快? 虎招少,有用的招就更少 不过,流星中有几种武器可以肆无忌惮的拿破防当主攻? 流星中有几种武器能让破防和非破防招如此的完美结合,滴水不漏? 能把这两点都容纳的,又有哪个武器? 只有虎 输给虎的人,都很生气,即使对手不粘也一样 为什么? 因为你是以“无防”的状态去对战的 相当于你没防御键 因为你防不防一个求样... 输了你

  • QQ钻皇上线,开通QQ钻黄 50元/月 享受QQ会员红黄蓝绿钻特权(king.qq.com) 2013-07-01

    QQ钻皇上线,开通QQ钻黄 50元/月 享受QQ会员红黄蓝绿钻特权(king.qq.com) 这个 QQ钻皇 去年发过的的 多年出了个官方微博。。 现在官方网站出来了 http://king.qq.com 点亮方法是 已经开通 QQ会员红黄蓝绿钻 的 自动点亮 看下图 貌似开通了上述服务 就是15星吧。。 = =! 猫猫第一名 不好意思截图下面 资费就是一起开通 QQ会员 红黄蓝钻 的钱 开通方式 钻皇特权详见 http://king.qq.com/tequan.html

  • Clash of Kings手游激活码领取 列王的纷争激活码礼包 2013-09-14

    列王的纷争Clash of Kings手游在国内没有官网,很多玩家都不知道在哪里领取游戏的激活码,其实很简单,西西还是为您找到了领取激活码礼包的地址哦,下边来为大家分享一下! Clash of Kings手游激活码领取》 礼包内容:150金?拧?5000木材、15000?食 兑换方式: 登???颍?c?羧宋镱^像,??Q?一?谥休?入??哟a?取 备注: 1.每????蚪巧?拗剖褂靡淮危?荒苤匮}使用 2.此?包?樽芳佣Y包,之前?取?的玩家不能重复?取?眩?/p> 手游礼包领取中心:ht

  • Burger King(汉堡王)品牌及包装设计 2013-09-15

      现在什么东西都讲求包装,食物更是如此,对于食品行业来说,商品拥有一个让人增进食欲的包装是很重要的,今天我们分享Burger King(汉堡王)品牌及包装设计,希望你们喜欢。

  • CodeForces 370A Rook, Bishop and King 2013-09-27

    A. Rook, Bishop and King time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Little Petya is learning to play chess. He has already learned how to move a king, a rook and a bishop. Let us remin

  • king战队介绍 king战队成员 2013-10-11

      king是一支非常年轻的lol战队,初次打lpl还是暴露了这支年轻战队的一些不足之处,不过对于king来说是一次非常难得的成长机会,希望king能够走向世界!现在让我们来认识一下这支战队的小伙伴们吧   King电子竞技俱乐部隶属于上海奋荣投资管理有限公司,成立于2013年10月,目前训练地址在上海。俱乐部采用军事化管理为主,引导选手树立正确目标为辅,强制与自觉相并进促使选手快速成长。   Skye   方启帆,意识顶尖的上单选手,非常擅长抗压,拥有非常强的抗压能力和防gank嗅觉。   M

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

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

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