01分数规划

N个数取k个，每个数都有a，b属性，最大化

\(\sum_{i\in{k}}{\frac{a_i}{b_i}}\)

可以二分答案\(mid\)

将式子化为

\(\sum_{i\in k}{a_i-mid*b_i}\)

如果此时最大值大于0

说明\(mid\)小于答案

反之亦然

最优比率生成树

最小化生成树的n条边

\(\frac{\sum_{i\in n} cost(i)}{\sum_{i\in n} dis(i)}\)

做法：二分答案+kruskal||Prim

最优比率环

找一个环，最大化xxx

二分答案，在图上转化为负环

最大权密度子图

\(MaximizeD=\frac{\sum_{e\in E}x_e}{\sum_{v\in V}x_v}\)

\(x_e,x_v\in0,1\)

( E:边集\(\quad\)V：点集 )

二分答案\(mid\)判断

求最大值可用最大权闭合子图，选一条边则必须选择两个顶点

建图

\(s-1->e-inf->u,v-g->t\)