杂项01 分数规划On this page01 分数规划参考资料 01 分数规划 - OI Wiki 简介 01 分数规划 求一个子集，使「选中元素的收益之和除以代价之和」最大或最小。二分答案 midmidmid，将每个元素的权值改为 收益−mid×代价收益-mid\times 代价收益−mid×代价，再判断是否存在子集使总权值非负，即把分式最优化转化为可行性判定。 例题 Problemcode洛谷 P3199 [HNOI2009] 最小圈给定一张 nnn 个点 mmm 条带权有向边的图，求一个环，使环上边权的平均值最小。