01分数规划

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\)，使得：

移项可得：

此时我们要对每一个 \(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\)，使得：

也就是说，将原来每条边的边权减去 \(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] 方伯伯运椰子

题目中的两种调整方式分别对应退流和增广。最优方案是在最大流不变的情况下使压缩、扩容总费用和最少。

更形式化点说，存在残量网络使得：

1. 扩容: \(u \rightarrow v\) 花费 \(b+d\)
2. 压缩:（反向边有流量）满足 \(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;
}

完结撒花 \ / \ / \ /

本栏目推荐文章
• P1763 埃及分数（100分Unaccepted) 被hack qwq
• 【题解】洛谷P1068 [NOIP2009 普及组] 分数线划定 （map）
• 2023.12.20闲话——对埃及分数的另一种做法（？）
• P1298 最接近的分数
• 类内 重载运算符 分数 加减乘除
• P1572 计算分数
• 1.10 05:分数线划定
• P8599 [蓝桥杯 2013 省 B] 带分数
• 2023-11-25：用go语言，给定一个数组arr，长度为n，表示n个格子的分数，并且这些格子首尾相连， 孩子不能选相邻的格子，不能回头选，不能选超过一圈， 但是孩子可以决定从任何位置开始选，也可以
• 消灭星星相关分数

分数带分数 分数线 百分数 最简分数 真分数 分数178 分数p1572 分数 等级 成绩 带分数8599 真分数 分数