POJ 2728 Desert King ★(01分数规划介绍 && 应用の最优比率生成树)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

【题意】每条路径有一个 cost 和 dist，求图中 sigma(cost) / sigma(dist) 最小的生成树。

标准的最优比率生成树，楼教主当年开场随手1YES然后把别人带错方向的题Orz……

♦01分数规划

参考Amber-胡伯涛神牛的论文《最小割模型在信息学竞赛中的应用》

°定义

分数规划（fractional programming）的一般形式：

Minimize λ = f(x) = a(x) / b(x) ( x∈S && ∀x∈S, b(x) > 0 )

其中，解向量x在解空间S内， a(x)与b(x)都是连续的实值函数。

分数规划的一个特例是0-1分数规划(0-1 fractional programming)，就是其解向量x满足∀x_i∈{0,1}（这就是所谓的0-1）。形式化定义如下：

Minimize λ = f(x) = a•x / b•x = sigma(a*x) / sigma(b*x) ( x∈{0,1}^n && b•x > 0 )

并且对解向量x可能还有其他的组合限制，这些针对解向量x的不同限制也就有了01分数规划的不同模型：比如最优比率生成树、最优比率生成环、最优比率割……

°解法

假设我们已经知道了最终答案λ，那么方程就可以写为： sigma(ax*) = sigma(bx*)•λ，即sigma(ax*) - sigma(bx*)•λ = 0

令g(λ) = min(x∈S){ sigma(ax) - λ•sigma(bx) }，易知该函数单调递减，且设*λ为该规划的最优解，则

g(λ) = 0 ⇔ λ = *λ

g(λ) > 0 ⇔ λ < *λ

g(λ) < 0 ⇔ λ > *λ

所以我们就可以二分枚举λ，然后判断g(λ)是否等于0……而g(λ)的计算要根据不同模型（即对x的不同限制）具体解决。

【Dinkelbach迭代算法】

不同于刚才的二分枚举，算法采用牛顿迭代的方式来求λ。

①初始设λ₀ = 0

②计算g(λ₀)，并且得到最优解*x

③计算*λ = a•*x / b•*x，如果*λ = λ₀，算法结束；否则令λ₀ = *λ，继续步骤②.

迭代比二分速度快很多，而且不用考虑二分的上界。

【最优比率生成树解法】

我们回到此题，就比如此题的最优比率生成树，二分枚举λ，那么就判断g(λ) = min(x∈S){ (cost-λ*dist)•x }是否等于0.

而计算g(λ)就是把原图中的每条边的权值都改为cost-λ*dist，然后求最小生成树即可.

#include
#include
//精度模板
const double eps = 1e-4;
bool dd(double x,double y) { return fabs( x - y ) dist[i]){
minx = dist[i];
u = i;
}
}
if (u == -1) break;
vis[u] = 1;
csum += cost[pre[u]][u];
lsum += len[pre[u]][u];
for (int i = 2; i w){
dist[i] = w;
pre[i] = u;
}
}
}
return csum / lsum;
}
int main(){
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
while(scanf("%d", &n), n){
for (int i = 1; i

POJ 2728 Desert King ★(01分数规划介绍 && 应用の最优比率生成树)的更多相关文章

POJ 2728 Desert King (01分数规划）
Desert King Time Limit: 3000MS Memory Limit: 65536K Total Submissions:29775 Accepted: 8192 Descr ...
POJ 2728 Desert King 01分数规划，最优比率生成树
一个完全图,每两个点之间的cost是海拔差距的绝对值,长度是平面欧式距离, 让你找到一棵生成树,使得树边的的cost的和/距离的和,比例最小然后就是最优比例生成树,也就是01规划裸题看这一发:ht ...
POJ 2728 Desert King | 01分数规划
题目: http://poj.org/problem?id=2728 题解: 二分比率,然后每条边边权变成w-mid*dis,用prim跑最小生成树就行 #include<cstdio> ...
poj2728 Desert King——01分数规划
题目:http://poj.org/problem?id=2728 第一道01分数规划题!(其实也蛮简单的) 这题也可以用迭代做(但是不会),这里用了二分: 由于比较裸,不作过多说明了. 代码如下: ...
01分数规划poj2728（最优比例生成树）
Desert King Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 21766 Accepted: 6087 Desc ...
【POJ2728】Desert King - 01分数规划
Description David the Great has just become the king of a desert country. To win the respect of his ...
poj2728 Desert King --- 01分数规划二分水果。。
这题数据量较大.普通的求MST是会超时的. d[i]=cost[i]-ans*dis[0][i] 据此二分. 但此题用Dinkelbach迭代更好 #include<cstdio> #in ...
【POJ2728】Desert King（分数规划）
[POJ2728]Desert King(分数规划) 题面 vjudge 翻译: 有\(n\)个点,每个点有一个坐标和高度两点之间的费用是高度之差的绝对值两点之间的距离就是欧几里得距离求一棵生成 ...
POJ 2728 Desert King（最优比率生成树 01分数规划）
http://poj.org/problem?id=2728 题意: 在这么一个图中求一棵生成树,这棵树的单位长度的花费最小是多少? 思路: 最优比率生成树,也就是01分数规划,二分答案即可,题目很简 ...

随机推荐

启动tomcat 报 Could not delete D&colon;/online/&period;metadata/&period;plugins/org&period;eclipse&period;wst&period;server&period;core/tm
aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAAAXkAAADkCAIAAADy7sNDAAAgAElEQVR4nO2deVQUV77H6z+haSeTkZ
烂泥：【解决】NFS服务器使用showmount –e命令报错
本文由秀依林枫提供友情赞助,首发于烂泥行天下. 今天在NFS服务器使用showmount –e查看NFS共享目录时,发现系统一直显示如下错误: clnt_create: RPC: Port mappe ...
Java反编译利器-Jad, Jode, Java Decompiler等及其IDE插件
转自:http://blog.csdn.net/superbeck/article/details/5189231 对于长年使用Java的程序员,大部分应该都会或多或少的使用到反编译软件.毕竟,不可能 ...
input标签写CSS时需要注意的几点（先收藏）
(从已经死了一次又一次终于挂掉的百度空间人工抢救出来的,发表日期2014-05-05) 飞鱼的声纳顶部的搜索框让我头疼了很长时间,原因是总不能获得跨浏览器的统一样式.主要的问题有这么两个:一是inpu ...
【转】NSDictionary以及NSMutableDictionary的用法
原文网址:http://my.oschina.net/u/1245365/blog/177736 摘要 Foundation中的字典是由键—值对组成的数据集合.通过key(键),查找对应的valu ...
老男孩python第六期
01 python s6 day7 上节回顾02 python s6 day7 SNMP使用03 python s6 day7 大型监控架构讲解04 python s6 day7 Redis使用05 ...
SQLPrompt&lowbar;7&period;2&period;2&period;273〖含注册机〗（支持低版本和最高版本SQL2016+VS2015）
SQLPrompt_7.4.1.564[含注册机](支持低版本和最高版本SQL2016+VS2015) http://download.csdn.net/detail/wozengcong/97601 ...
关于array&period;sort(array,array)
// 基于第一个 System.Array 中的关键字,使用每个关键字的 System.IComparable 实现,对两个一维 System.Array // 对象(一个包含关键字,另一个包含对应的 ...
BZOJ 1345[BOI]序列问题 - 贪心 + 单调栈
题解真的没有想到是单调栈啊. 回想起被单调栈支配的恐惧最优情况一定是小的数去合并尽量多的数,所以可以维护一个递减的单调栈. 如果加入的数比栈首小, 就直接推入栈. 如果加入的数大于等于栈首, 必 ...
git移除文件夹的版本控制
案例背景:git提交的时候把bin文件下的各种.dll提交上去了,然后每次提交都得提交好多文件,很容易忽略你真正修改的东西,故对这些不必要的东西忽略掉解决方案:git rm 命令参数具体实施: 1 ...