AcWing 361 观光奶牛

题目传送门

一、01分数规划

\(01\)分数规划是这样的一类问题:有一堆物品，每一个物品有一个收益\(a_i\)，一个代价\(b_i\)，我们要求一个方案使选择的\(∑a_i / ∑b_i\) 最大。

比如说在\(n\)个物品中选\(k\)个物品，使得\(∑a_i / ∑b_i\) 最大，并且我们知道\(a_i\)和\(b_i\)的范围，间接就知道了\(∑a_i / ∑b_i\) 的范围，有范围的问题如果再具有单调性就可以用二分解决，如果我们能够知道对于某个\(mid\)，存在\(∑a_i / ∑b_i >= mid\)，就说明最终的解不小于\(mid\)了，这就是本问题的单调性。

要使\(∑a_i / ∑b_i >= mid\)，只要\(mid * ∑b_i <= ∑a_i\)即可，即\(∑(mid*b_i - a_i) <= 0\)，所以可以按照 \(mid*b_i - a_i\)的大小排序，前\(k\)个物品之和小于\(0\)就说明这样的\(mid\)是存在的了。

二、本题思路

对于本题而言，既存在点权又存在边权不好计算。要使\(∑f_i / ∑t_i\)最大，只需要像上面解决一般的\(01\)分数规划问题那样二分即可，如果\(∑(mid*t_i - f_i) <= 0\)，就说明这样的\(mid\)存在。

本题又是求图中一个环上的点满足这样的条件，所以本质上就是看有没有负权回路存在。一般的\(01\)规划问题\(a_i\)和\(b_i\)一一对应，而本题中一个点可能连接多条边，但是一条边有且仅有两个顶点，我们可以把每个顶点都收缩到它的各条出边上（收缩到入边上也是一样道理）。或者说，原图中有点权\(f[i]\)，边权\(t[i]\)，我们现在是要构造一张新图，新图的边权为\(mid*t_i - f_i\)，只要这张新图存在负权回路，就说明这样的\(mid\)是存在的。

另外需要注意的是\(mid\)的取值是浮点数，我们在对浮点数做二分时，\(mid\)不能随便加减一了，不论存不存在这样的\(mid\)，\(l\)或者\(r\)都只能等于\(mid\)，整数二分的上下取整问题对于浮点数二分也是不存在的。

本题虽然看起来复杂，但是只需要对图的边权做下映射，很容易发现就是求图中有没有负环的问题，解决起来还是比较简单的，总的代码如下：

三、求负环实现代码

#include 
using namespace std;
const int N = 1010, M = 5010;
int n, m;
int f[N], cnt[N];
double dist[N];
bool st[N];

//邻接表
int idx, h[N], e[M], w[M], ne[M];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool check(double mid) {
    queue q;
    memset(cnt, 0, sizeof cnt);
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);
    for (int i = 1; i <= n; i++) {
        q.push(i);
        st[i] = true;
    }
    while (q.size()) {
        int u = q.front();
        q.pop();
        st[u] = false;
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[u] + w[i] * mid - f[u]) {
                dist[j] = dist[u] + w[i] * mid - f[u];
                //判负环
                cnt[j] = cnt[u] + 1;
                if (cnt[j] >= n) return true;
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> f[i]; //每个点都有一个权值f[i]
    //初始化邻接表
    memset(h, -1, sizeof h);
    int a, b, c;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        add(a, b, c);
    }
    //浮点数二分
    double l = 0, r = 1000;
    //左边界很好理解，因为最小是0；
    //右边界即使f[i]=1000,有1000个，那么t[i]也有1000个，最大还是1000
    //因为保留两位小数，所以这里精度设为1e-4
    while (l < r - 1e-4) {
        double mid = (l + r) / 2;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    printf("%.2lf\n", l);
    return 0;
}

四、正环思路与解法

求图中是否存在正环，和求负环是一个对称问题，直接更改\(spfa\)算法中的不等号方向，转而变成求最长路算法中是否存在正环，即可办到。

#include 
using namespace std;
const int N = 1010, M = 5010;
int n, m;
int f[N], cnt[N];
double dist[N];
bool st[N];

//邻接表
int idx, h[N], e[M], w[M], ne[M];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool check(double mid) {
    queue q;
    memset(cnt, 0, sizeof cnt);
    memset(dist, 0x3f, sizeof dist);
    memset(st, false, sizeof st);
    for (int i = 1; i <= n; i++) {
        q.push(i);
        st[i] = true;
    }
    while (q.size()) {
        int u = q.front();
        q.pop();
        st[u] = false;
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            //正环还是负环，区别在这里
            if (dist[j] < f[u] + dist[u] - w[i] * mid) {
                dist[j] = f[u] + dist[u] - w[i] * mid;
                //判正环
                cnt[j] = cnt[u] + 1;
                if (cnt[j] >= n) return true;
                if (!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> f[i]; //每个点都有一个权值f[i]
    //初始化邻接表
    memset(h, -1, sizeof h);
    int a, b, c;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        add(a, b, c);
    }
    //浮点数二分
    double l = 0, r = 1000;
    //左边界很好理解，因为最小是0；
    //右边界即使f[i]=1000,有1000个，那么t[i]也有1000个，最大还是1000
    //因为保留两位小数，所以这里精度设为1e-4
    while (l < r - 1e-4) {
        double mid = (l + r) / 2;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    printf("%.2lf\n", l);
    return 0;
}