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