01分数规划属于二分法的一个应用，主要用于解决有关 “最优比率” 的问题，如最优比率背包、最优比率生成树等。
题目大致是说，给定两个长度均为 \(n\) 的数组 \(a、b\)，要从中选出 \(k\) 组 \(a\) 和 \(b\)，求 \(max\dfrac{\sum_{i=1}^na_is_i}{\sum_{i=1}^nb_is_i}\)。其中 \(s_i =0\)(不选) 或 \(s_i=1\)(选)，且 \(\sum_{i=1}^ns_i=k\)。
考虑如何求解。
最暴力的方法就是二进制枚举，复杂度 \(O(2^n)\)，时间太劣。
我们考虑去猜数，猜测所求的值 \(c\)，使得：
\[\dfrac{\sum_{i=1}^na_is_i}{\sum_{i=1}^nb_is_i} \geq c \]移项可得：
\[\sum_{i=1}^na_is_i \geq c \times \sum_{i=1}^nb_is_i \]\[\sum_{i=1}^na_is_i \geq \sum_{i=1}^n(c\times b_is_i) \]\[\sum_{i=1}^n(a_is_i-c\times b_is_i) \geq 0 \]\[\sum_{i=1}^ns_i(a_i-c\times b_i) \geq 0 \]此时我们要对每一个 \(i\) 求出 \(a_i - c\times b_i\)，记为 \(d_i\)。那么显然，取 \(d_i\) 最大的 \(k\) 个元素最优。
此外，当 \(c\) 单调递增时，\(d_i\) 是单调递减的。于是我们可以通过二分提高猜数的效率，大幅缩短程序运行时间。
总时间复杂度 \(O(n\log n)\)
P4377 [USACO18OPEN] Talent Show G
这道题将01分数规划与01背包结合，求 \(max\dfrac{\sum_{i=1}^nt_is_i}{\sum_{i=1}^nw_is_i}\)，此外还有 \(\sum_{i=1}^nw_is_i\geq W\) 的限制。
因为 \(\sum_{i=1}^nw_is_i\) 可以大于 \(W\)，所以在统计背包的时候，要将大于 \(W\) 的背包容量统一成 \(W\) 记录下来。
最后如果 \(f_W <0\)，说明答案估大了，否则估小了。
代码：
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int kmax = 255;
const int kmaxM = 1005;
struct Cow {
int w, t;
double v;
} c[kmax];
int n, w;
double l, r;
double f[kmaxM];
bool Check(double x) {
for (int i = 1; i <= n; i++) {
c[i].v = c[i].t - x * c[i].w; // 求值
}
f[0] = 0;
for (int i = 1; i <= w; i++) {
f[i] = -1e18;
}
for (int i = 1; i <= n; i++) { // 背包
for (int j = w; ~j; j--) {
f[min(w, j + c[i].w)] = max(f[min(w, j + c[i].w)], f[j] + c[i].v);
}
}
return f[w] < 0;
}
int main() {
cin >> n >> w;
for (int i = 1; i <= n; i++) {
cin >> c[i].w >> c[i].t;
r += c[i].t; // 计算上限
}
for (int i = 1; i <= 60; i++) { //限制二分次数
double mid = (l + r) / 2.0;
if (Check(mid)) {
r = mid;
} else {
l = mid;
}
}
cout << (long long)(1000ll * l);
return 0;
}
P4322 [JSOI2016] 最佳团体
这道题要在01分数规划下做树上背包。
记 \(f_{x,y}\) 表示在 \(x\) 的子树中一共选 \(y\) 个人最大的结果。
注意 \(0\) 号点要算进去，共选 \(m+1\) 人，\(dp\) 的终态是 \(f_{0, m+1}\)。
代码：
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
const int kmax = 2505;
const double eps = 1e-4; // 精度
struct Person {
int c, p;
double v;
} p[kmax];
int m, n;
int siz[kmax];
double l, r;
double f[kmax][kmax];
vector<int> e[kmax];
void Dfs(int x, int fa) {
f[x][1] = p[x].v; // 只选他自己一个人
siz[x] = 1;
for (int y : e[x]) {
if (y == fa) continue;
Dfs(y, x);
for (int i = min(m + 1, siz[x] + siz[y]); i; i--) {
for (int j = 0; j <= min(i - 1, siz[y]); j++) {
f[x][i] = max(f[x][i], f[x][i - j] + f[y][j]);
}
}
siz[x] += siz[y];
}
}
bool Check(double x) {
for (int i = 1; i <= n; i++) {
p[i].v = p[i].p - x * p[i].c;
}
for (int i = 0; i <= n; i++) {
for (int j = 1; j <= m + 1; j++) {
f[i][j] = -1e18;
}
}
Dfs(0, 0);
return f[0][m + 1] <= 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> m >> n;
for (int i = 1, x; i <= n; i++) {
cin >> p[i].c >> p[i].p >> x;
e[x].push_back(i);
r += p[i].p;
}
for (double mid; l + eps < r;) {
mid = (l + r) / 2.0;
if (Check(mid)) {
r = mid;
} else {
l = mid;
}
}
cout << fixed << setprecision(3) << l;
return 0;
}
P3199 [HNOI2009] 最小圈
简化题意：给定一张有向图，定义一个环的价值为环上边的边权平均值，求这张图所有环的价值最小值。
假设一个环有 \(k\) 条边，其权值为 \(\dfrac{\sum_{i=1}^kw_k}{k}\)，我们猜测一个数 \(x\)，使得：
\[\dfrac{\sum_{i=1}^kw_k}{k}\leq x \]\[\sum_{i=1}^kw_k\leq kx \]\[(\sum_{i=1}^kw_k)-kx\leq 0 \]\[\sum_{i=1}^k(w_k-x)\leq 0 \]也就是说，将原来每条边的边权减去 \(x\) 后，如果有向图中存在负环，不等式是合法的。
这里同样可以采用二分提高效率。
判负环时以每个点为起点，如果对同一点更新了多次答案，说明存在负环。
代码：
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
const int kmax = 3005;
const double eps = 1e-9;
struct E {
int y;
double w;
};
int n, m;
double l = -1e6, r = 1e6;
double d[kmax];
bool b[kmax], o;
vector<E> e[kmax];
void Spfa(int x, double k) {
b[x] = 1;
for (auto cur : e[x]) {
int y = cur.y;
double w = cur.w - k;
if (d[y] > d[x] + w) {
d[y] = d[x] + w;
if (b[y]) {
o = 1;
return;
}
Spfa(y, k);
}
}
b[x] = 0;
}
bool Check(double k) {
o = 0;
memset(b, 0, sizeof(b));
memset(d, 0, sizeof(d));
for (int i = 1; i <= n && !o; i++) {
Spfa(i, k);
}
return o;
}
int main() {
cin >> n >> m;
for (int i = 1, x, y; i <= m; i++) {
double w;
cin >> x >> y >> w;
e[x].push_back({y, w});
}
for (double mid; l + eps < r;) {
mid = (l + r) / 2.0;
if (Check(mid)) {
r = mid;
} else {
l = mid;
}
}
cout << fixed << setprecision(8) << r << '\n';
return 0;
}
P3288 [SCOI2014] 方伯伯运椰子
题目中的两种调整方式分别对应退流和增广。最优方案是在最大流不变的情况下使压缩、扩容总费用和最少。
更形式化点说，存在残量网络使得：
- 扩容: \(u \rightarrow v\) 花费 \(b+d\)
- 压缩:（反向边有流量）满足 \(c>0\) 时 \(v \rightarrow u\) 花费 \(a-b\)
然后套用分数规划，同上题思路判负环即可。
为什么可行，需要借助一个定理 —— 消圈定理。
在某个流 \(f\) 中，若它对应的残余网络没有负环，那么它一定就是当前流量下的最小费用流。
代码：
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
const int kmax = 5005;
const double eps = 1e-4;
struct E {
int y;
double w;
};
int n, m;
vector<E> e[kmax];
bool b[kmax], o;
double d[kmax];
void Spfa(int x, double k) {
b[x] = 1;
for (auto cur : e[x]) {
int y = cur.y;
double w = cur.w + k;
if (d[y] > d[x] + w) {
d[y] = d[x] + w;
if (b[y]) { // 再次被更新
o = 1; // 说明存在负环
return;
}
Spfa(y, k);
}
}
b[x] = 0;
}
bool Check(double k) {
memset(b, 0, sizeof(b));
memset(d, 0, sizeof(d));
o = 0;
for (int i = 1; i <= n && !o; i++) {
Spfa(i, k); // 判负环
}
return o;
}
double Search() { // 二分
double l = 0, r = 1e9;
for (double mid; l + eps < r;) {
mid = (l + r) / 2.0;
if (Check(mid)) {
l = mid;
} else {
r = mid;
}
}
return l;
}
int main() {
cin >> n >> m;
n += 2;
for (int i = 1, x, y, a, b, c, d; i <= m; i++) {
cin >> x >> y >> a >> b >> c >> d;
e[x].push_back({y, (double)(b + d)}); // 建边
if (c > 0) e[y].push_back({x, (double(a - d))});
}
cout << fixed << setprecision(2) << Search();
return 0;
}
完结撒花 \ / \ / \ /
标签：分数,01,int,double,sum,mid,kmax,include,规划 From： https://www.cnblogs.com/ereoth/p/17561499.html