[WC2010][BZOJ1758]重建计划-[二分+分数规划+点分治]
Description 传送门 Solution 看到那个式子，显然想到分数规划。。。（不然好难呢） 然后二分答案，则每条边的权值设为g(e)-ans。最后要让路径长度在[L,U]范围内的路径权值>=0 接下来我们就要找路径了。。 考虑树形dp或者分治。 假如是树形dp需要用长链剖分优化。 我...
BZOJ5281: [Usaco2018 Open]Talent Show 01分数规划+01背包
DescriptionFarmerJohn要带着他的N头奶牛，方便起见编号为1…N，到农业展览会上去，参加每年的达牛秀！他的第i头奶牛重量为wi，才艺水平为ti，两者都是整数。在到达时，FarmerJohn就被今年达牛秀的新规则吓到了： （一）参加比赛的一组奶牛必须总重量至少为W （这是为了确保是强...
01分数规划poj2728（最优比例生成树）
Desert KingTime Limit: 3000MS Memory Limit: 65536KTotal Submissions: 21766 Accepted: 6087DescriptionDavid the Great has just become the king of a dese...
zju2676 Network Wars 分数规划+网络流
题意：给定无向图，每条边有权值，求该图的一个割集，是的该割集的平均边权最小Amber的《最小割模型在信息学竞赛中的应用》中讲的很清楚了。二分答案k，对每条边进行重新赋值为原边权-k，求最大流，可看这里：http://hi.baidu.com/buaa_babt/item/a08fbb45599dc7...
网络流（最大密集度子图，分数规划）：UvaLive 3709 Hard Life
JohnisaChiefExecutiveOfficerataprivatelyownedmediumsizecompany.TheownerofthecompanyhasdecidedtomakehissonScottamanagerinthecompany.Johnfearsthattheown...
2018.10.19 NOIP训练 yk赚钱记（01分数规划）
传送门其实是一个裸的最优比率生成树。注意精度的控制就行了。代码2018.10.19NOIP训练yk赚钱记（01分数规划）的更多相关文章2018.10.19NOIP训练变化的序列（线性dp）传送门f[i][j]f[i][j]f[i][j]表示后iii个对答案...
BZOJ 4753 [Jsoi2016]最佳团体 | 树上背包 分数规划
BZOJ4753[Jsoi2016]最佳团体|树上背包分数规划又是一道卡精度卡得我头皮发麻的题……题面（……蜜汁改编版）YL大哥是24OI的大哥，有一天，他想要从\(N\)个候选人中选\(K\)个小弟（\(N,K\le2500\))。想要成为大哥的小弟不是件容易事，必须要有一个举荐人才行，所以每个候...
poj 3266 Cow School 分数规划
这个题目难度非常大，首先对于老师的一种方案，应用分数规划的一般做法，求出所有的c=t-rate*p，如果没有选择的c值中的最大值比选择了的c值中的最小值大，那么这个解是可以改进的。那么问题就转化成了怎么求最小的c和最大的c。t-rate*p求这种类型的最值，并且rate是单调的，那么就可以考虑利用斜...
POJ2976 Dropping tests 01分数规划
裸题看分析请戳这里：http://blog.csdn.net/hhaile/article/details/8883652#include<stdio.h>#include<algorithm>usingnamespacestd;constintN=1e3+;constdou...
BZOJ_4476_[Jsoi2015]送礼物_01分数规划+单调队列
BZOJ_4476_[Jsoi2015]送礼物_01分数规划+单调队列DescriptionJYY和CX的结婚纪念日即将到来，JYY来到萌萌开的礼品店选购纪念礼物。萌萌的礼品店很神奇，所有出售的礼物都按照特定的顺序都排成一列，而且相邻的礼物之间有一种神秘的美感。于是，JYY决定从中挑选连续的一些礼物...
4819: [Sdoi2017]新生舞会 分数规划
题目https://www.lydsy.com/JudgeOnline/problem.php?id=4819思路分数规划的模板题？(好菜呀)假如n=3吧(懒得写很长的式子)\(c=\frac{a_1+a_2+a_3}{b_1+b_2+b_3}\)我们先二分一下，变为判定性问题c是否大于等于xxxx...
【POJ2976】Dropping Tests（分数规划）
【POJ2976】DroppingTests（分数规划）题面Vjudge翻译在\(Vjudge\)上有（而且很皮）题解简单的\(01\)分数规划需要我们做的是最大化\(\frac{\suma[i]}{\sumb[i]}\)考虑二分答案将最大化问题转换为判定问题\(\sum{a[i]}-mid\sum...
POJ 2728 Desert King 01分数规划，最优比率生成树
一个完全图，每两个点之间的cost是海拔差距的绝对值，长度是平面欧式距离，让你找到一棵生成树，使得树边的的cost的和/距离的和，比例最小然后就是最优比例生成树，也就是01规划裸题看这一发：http://blog.csdn.net/sdj222555/article/details/7490797#...
POJ - 2976 Dropping tests && 0/1 分数规划
POJ-2976Droppingtests你有\(n\)次考试成绩，定义考试平均成绩为$$\frac{\sum_{i=1}^{n}a_{i}}{\sum_{i=1}^{n}b_{i}}$$你可以考虑放弃\(K\)次成绩，求最大平均成绩*100小插曲：被精度卡成喜羊羊0/1分数规划\(from\)人生...