模型
求一个分数表达式的最大（小）值
有 $n$ 个物品，每个物品有两个权值 $value$ 和 $cost$ ，
然后让你选出任意件数（但可能会有限制）的物品，
使得两个权值和间的比值最大，即求 $\dfrac{\sum_{i=1}^{k} value[i]}{\sum_{j=1}^{k} cost[j]}$的最大值
（在这里 $1-k$ 为挑出的 $k$ 件物品）
选择物品方面给出一定的限制条件
方法
二分
以上面的式子为例，并添加上限制 $k \geq W$
令 $sum=\sum_{i=1}^{k} value[i]$ , $tot= \sum_{j=1}^{k} cost[j],k\geq W$
然后假设问题中的最优解为 $ans$ ，那么必然有：
移项得：
继续移就得到：
将 $sum$ 和 $tot$ 带回去:
所以二分这个 $ans$ ，排序，贪心，取前 $W$ 个，重新二分
(玄学的)Dinkelbach 算法
咕了
例题
裸题
最优比例背包
对于条件的判断方式改为了0/1背包
对每个物品，体积 $cost$ ，价值是 $value_i-cost_i*ans$
跑个背包判断是否满背包即可
最优比率生成树
模型
带权无向图 $G$ ， 对于图中每条边 $e_i$，
都有 $value_i$ 和 $cost_i$，
现在求一棵生成树 $T$ ，最大（小）化
解法
若 $e_i\in T$ 则 $x_i=1$ 否则 $x_i=0$
二分答案 $r$ ，边赋值 $weight_i = value_i-r\cdot cost_i$ ，
因为是生成树，边的数量确定，那么 $max\{f(r)\}$ 需要选取前 $|G| -1$ 大的 $weight_i$ ，
也就是求最大生成树，按最大生成树权值的正负性就可以二分了。
最小化就求最小生成树。
例题
最优比率环
模型
给定有点权和边权的图，求一个环，使得环的点权和与边权和的比值最大。
点权为 $value_i$ ，边权为 $cost_i$ ，一个环为 $C$
问题要求最大化
（表述不严谨，将就看）解法
设当前答案 $r$ ，
$r \leq r^*$ ，至少存在一个环，$r \cdot \sum cost_i - \sum value_i \leq 0$ ，
即存在负权回路（将边权设为 $r\cdot cost_i-value_i$ ，不是提前算出，而是在更新路径的时候从哪个点访问到这条边的就将这条边设为相应点权与边权的对应值）；
$r \geq r^*$ ，则不存在负环。
求负环用 spfa 算法
具体判断方法为，一个点不能入队 $n$ 次，否则有负环；一条最短路径长度不能到 $n$ ，否则有负环。
两个判断方法可以同时使用。
最小化时边权设为 $\sum value_i -r \cdot \sum cost_i$
即可，同样也是更新时算出此值。例题
最大密度子图
不想打Latex了然而还是又打上了在一个无向图 $G$ 里找一个子图 $G^{‘}$ 使得
推波式子
二分 $mid \leq \frac{ \sum edge_i}{ \sum vertex_i}$
再考虑优化
把边数看成 $(至少有一点在 G^{‘} 内的边) - (只有一点在 G^{‘} 内的边)$
只有一点在 $G^{‘}$ 内的边相当于 $G^{‘}$ 与其补集的最小割
设 $h(x)=\max (\sum edge_i \space - \space \sum vertex_i \cdot mid)$
那么目的就是最大化 $h(x)$
转化为求 $\min ( \space -h(x)
\space)$可以推出建图方法
每条原图的边 $(u,v)$ : $\text{u,v}$之间连无向边
超级源点 $S$ 向点 $i$ 连一条容量为 $U$ 的边 ($U$ 是一个足够大的数，一般取总边数 $m$)
每个点向超级汇点 $T$ 连一条容量为 $U+2 \cdot mid -度数$
注
这一部分与图论，尤其是最小割联系很紧密，
可以考虑参看 2007胡伯涛论文：《最小割模型在信息学竞赛中的应用》
例题
qwq最小割建模好难于是全交到uva上就不会掉洛谷AC率了qwq
最优比例流
-
咕了