python

13 KiB

Raw Permalink Blame History Unescape Escape

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

`AcWing` `361` 观光奶牛

一、题目描述

背景作为对奶牛们辛勤工作的回报，Farmer John决定带她们去附近的大城市玩一天。旅行的前夜，奶牛们在兴奋地讨论如何最好地享受这难得的闲暇。很幸运地，奶牛们找到了一张详细的城市地图，上面标注了城市中所有L(2⩽L⩽1000)座标志性建筑物（建筑物按1…L顺次编号）,以及连接这些建筑物的P(2⩽P⩽5000)条道路。按照计划，那天早上Farmer John会开车将奶牛们送到某个她们指定的 建筑物 旁边，等奶牛们 完成她们的整个旅行并回到出发点 后，将她们接回农场。由于大城市中总是寸土寸金，所有的道路都很窄，政府不得不把它们都设定为通行方向固定的 单行道。

尽管参观那些标志性建筑物的确很有意思，但如果你认为奶牛们同样享受穿行于大城市的车流中的话，你就大错特错了。与参观景点相反，奶牛们 把走路定义为无趣 且令她们厌烦的活动。对于编号为i的标志性建筑物，奶牛们清楚地知道参观它能给自己带来的乐趣值F_i(1⩽F_i⩽1000)。相对于奶牛们在走路上花的时间，她们参观建筑物的耗时可以忽略不计。

奶牛们同样仔细地研究过城市中的道路。她们知道第i条道路两端的建筑物L1_i和L2_i（道路方向为L1_i \rightarrow L2_i ）,以及她们从道路的一头走到另一头所需要的时间Ti(1⩽Ti⩽1000)。为了最好地享受她们的休息日，奶牛们希望她们 在一整天中平均每单位时间内获得的乐趣值最大 。当然咯，奶牛们不会愿意把同一个建筑物参观两遍，也就是说，虽然她们可以两次经过同一个建筑物，但她们的乐趣值只会增加一次。顺便说一句，为了让奶牛们得到一些锻炼，Farmer John要求奶牛们参观至少2个建筑物。请你写个程序，帮奶牛们计算一下她们能得到的最大平均乐趣值。

二、抽象题意

给定一张 L 个点、P 条边的 有向图，每个点都有一个权值 f[i]，每条边都有一个权值 t[i]。

求图中的一个环，使 环上各点的权值之和 除以 环上各边的权值之和 最大

输出这个 最大值。

注意：数据保证至少存在一个环

输入格式 第一行包含两个整数 L 和 P。

接下来 L 行每行一个整数，表示 f[i]。

再接下来 P 行，每行三个整数 a，b，t[i]，表示点 a 和 b 之间存在一条边，边的权值为 t[i]。

输出格式 输出一个数表示结果，保留两位小数。

数据范围 2≤L≤1000,2≤P≤5000,1≤f[i],t[i]≤1000

输入样例：

输出样例：

6.00

样例对应的图示：

二、解题思路

`01`分数规划

本题考察01分数规划。01分数规划是这样的一类问题:

有一堆物品，每一个物品有一个收益a_i，一个代价b_i，我们要求一个方案使选择的\sum{a_i} / \sum{b_i} 最大。比如说在n个物品中选k个物品，使得\sum{a_i} / \sum{b_i} 最大，并且我们知道a_i和b_i的范围，间接就知道了\sum{a_i} / \sum{b_i} 的范围，有范围的问题如果再具有单调性就可以用二分解决，如果我们能够知道对于某个mid，存在\sum{a_i} / \sum{b_i} >= mid，就说明最终的解不小于mid了，这就是本问题的 单调性。要使\sum{a_i} / \sum{b_i} >= mid，只要mid * \sum{b_i} <= \sum{a_i}即可，即\large \sum(mid*b_i - a_i) <= 0$，所以可以按照 $mid*b_i - a_i的大小【由小到大】排序，前k个物品之和小于0,就说明这样的mid是存在的。

注：如果对01分数规划还不是很清晰，需要再看一下 专题讲解

题目解析

f[i]:收益, w[i]:代价

对于本题而言，既存在点权又存在边权不好计算。要使∑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，整数二分的上下取整问题对于浮点数二分也是不存在的。

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

时间复杂度 最坏情况存在长度为 L 的环， ∑t_i=L,∑f_i=1000L。故答案最大可能是 1000。

疑问：有没有可能是零环呢？

A：因为这是一个浮点数的二分问题，不存在绝对相等，有精度的要求，也就不考虑零环问题。

三、二分 + 负环 + `SPFA`

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
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 x) {
    queue<int> 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] = 1;
    }

    while (q.size()) {
        int u = q.front();
        q.pop();
        st[u] = 0;
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            // 最短路
            if (dist[v] > dist[u] + w[i] * x - f[u]) {
                dist[v] = dist[u] + w[i] * x - f[u];
                // 判负环
                cnt[v] = cnt[u] + 1;
                if (cnt[v] >= n) return 1;
                if (!st[v]) {
                    q.push(v);
                    st[v] = 1;
                }
            }
        }
    }
    return 0;
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &f[i]); // 每个点都有一个权值f[i]

    // 初始化邻接表
    memset(h, -1, sizeof h);
    int a, b, c;
    while (m--) {
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c);
    }

    // 浮点数二分
    double l = 0, r = INF;
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid))
            l = mid; // 存在负环时，mid再大一点,最终取得01分数规则的最大值
        else
            r = mid; // 不存在负环时，mid再小一点
    }
    printf("%.2lf\n", l);
    return 0;
}

四、`SPFA+dfs`解法

Q:为什么要研究SPFA+dfs写法？答：如果你用SPFA的bfs写法判断负环出现了TLE，那么可以尝试使用SPFA+dfs写法，SPFA+dfs的方法可以做到线性时间复杂度，原理见：这里

dfs思路

① 把dist数组的初值置为0，这样就能保证走过的路径和一直为负，排除了大量无关路径。 ② 这样判断的是是否有经过起始点的负环，因此要判断整个图中是否有负环的话，得把n个点全跑一遍。

注意事项

① 如果 只是判负环，使用dfs比bfs一般要 快得多
② dfs 判断负环时，dist数组初值应该都设为0
③ 不要指望dfs在判断负环的同时还能求最短路了
④ 用dfs判断负环，不能只把一个点作为源点跑一次，而要把1−n每个都作为源点跑一遍dfs，才能保证结果的正确。

#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 5010;
int n, m;
int f[N], cnt[N];
double dist[N];
bool st[N];
const double eps = 1e-4;
// 邻接表
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++;
}

// dfs 判环 Accepted	35 ms
bool dfs(int u, double mid) {
    if (st[u]) return 1; // 如果又见u，说明有环
    bool flag = 0;       // 我的后代们是不是有环？

    st[u] = 1; // u出现过了~
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        // 更新最小值，判负环
        if (dist[v] > dist[u] + w[i] * mid - f[u]) {
            dist[v] = dist[u] + w[i] * mid - f[u];
            // 检查一下我的下一个节点v,它要是有负环检查到，我也汇报
            flag = dfs(v, mid);
            if (flag) break;
        }
    }
    st[u] = 0; // 回溯

    return flag;
}

bool check(double mid) {
    memset(dist, 0, sizeof dist);
    for (int i = 1; i <= n; i++)
        if (dfs(i, mid)) return true;
    return false;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &f[i]); // 每个点都有一个权值f[i]
    // 初始化邻接表
    memset(h, -1, sizeof h);
    int a, b, c;
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c);
    }
    // 浮点数二分
    double l = 0, r = 1000;
    // 左边界很好理解，因为最小是0；
    // Σf[i]最大1000*n,Σt[i]最小是1*n,比值最大是1000
    // 当然，也可以无脑的设置r=INF，并不会浪费太多时间，logN的效率你懂的
    // 因为保留两位小数，所以这里精度设为1e-4
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    printf("%.2lf\n", l);
    return 0;
}

疑问与解答

Q:为什么在dfs找负环的代码中，需要用到st[]的回溯呢，是为了不重新进行memset清零吗？还是有其它的理由？

答：找负环的代码是一个标准模板，必须回溯，不能用memset(st,0,sizeof st)进行替换，原因如下：

下面附上 标准模板代码 与 标准错误代码

#include <bits/stdc++.h>

using namespace std;
const int N = 1010, M = 5010;
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++;
}

// ① dfs找负环的标准模板
bool dfs1(int u) {
    if (st[u]) return 1;
    bool flag = 0;
    st[u] = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (dist[v] > dist[u] + w[i]) {
            dist[v] = dist[u] + w[i];
            flag = dfs1(v);
            if (flag) break;
        }
    }
    // 回溯写法
    st[u] = 0;
    return flag;
}

// ② 标准错误答案
bool dfs2(int u) {
    if (st[u]) return 1;
    bool flag = 0;
    st[u] = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (dist[v] > dist[u] + w[i]) {
            cout << "u=" << u << ",v=" << v << endl;
            dist[v] = dist[u] + w[i];
            flag = dfs2(v);
            if (flag) return 1;
        }
    }
    // 坚决不回溯

    return flag;
}

/*
测试用例：
4 4
1 2 -2
2 3 -6
2 4 1
4 3 -4

结论：图中是没有负环的，应该返回0
*/
int main() {
#ifndef ONLINE_JUDGE
    freopen("361.in", "r", stdin);
#endif
    int n, m;
    scanf("%d %d", &n, &m);
    // 初始化邻接表
    memset(h, -1, sizeof h);
    int a, b, c;
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c);
    }

    cout << dfs1(1) << endl; // 返回正确解0，表示没有找到负环

    // 如果按不回溯，而是memset的办法，结果就是错误的啦~
    memset(st, 0, sizeof st);
    memset(dist, 0, sizeof dist);
    cout << dfs2(1) << endl; // 返回错误结果1，表示找到负环
    return 0;
}

13 KiB Raw Permalink Blame History Unescape Escape

AcWing 361 观光奶牛