P1768 天路(P1768 Tianlu Road)

一种完全使用裸 SPFA 算法的做法。

一道分数规划题,实际上是最短路的灵活运用。

题意

题目话很多,简单来说就是:

\(n\) 个点,\(m\) 条边,每条边有两个属性,分别为花费 \(\text{cost}\) 和收益 \(\text{joy}\)。求出一个环使得环上的 \(\dfrac{\sum\text{joy}}{\sum \text{cost}}\) 的值最大。

思路

如果我们令答案为 \(p\),则对于图上任意一个环,都有:

将不等式左右两边乘上 \(\sum\text{cost}\),则:

换个位置可得:

也就是说,\(p\) 是正确的答案时,图上不会出现负环。

对于第 \(i\) 条边而言,在跑 SPFA 算法的时候,他实际的边权应该是

另外,我们可以发现,题目要求的是一个式子的值最大。观察 \(p\times \sum\text{cost}-\sum\text{joy}\) 发现这个式子是具有单调性的,那么就可以使用二分减少计算次数(从 \(200\) 次计算下降到了 \(\log_2(200)\approx8\) 次)

而且,在这道题中,题目并没有告诉我们起点是那个点。因此,我们需要建立一个超级源点(我的代码中是 \(0\) 号点),然后将他与其他 \(n\) 个点连接一条不会对答案产生影响的边。

最后,我罗列一下需要注意的几个点:

  • SPFA 的 \(\text{d}\) 数组需要是 bool 类型的,而且不能使用 memset 进行赋值,必须使用 for 循环暴力赋值。
  • 二分左端点初始为 \(1\),右端点初始设置为一个大于等于 \(200\) 的数。
  • 当二分结束后,左端点是等于 \(0\) 时,那么代表无解,输出 \(-1\)。

你以为结束了?并没有。

当你交上上面思路写出的代码时,你会发现你只有 90 分。

上面的思路唯一可以再减少操作步数的就只有 SPFA 内部了。我们设置一个值 \(\text{delta}\) 表示当一个点入队次数上限,进行人肉二分,发现当 \(\text{delta}\) 等于 \(10\) 的时候就可以通过此题,而且跑的飞快,总共只有 67ms,成功进入最优解第一页。

代码

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<iomanip>
using namespace std;

const int maxn = 7010;
const double eps = 1e-3;

int n, m;

struct node {
    int v, joy, cost;
    node(int vv, int jjoy, int ccost) {
        v = vv, joy = jjoy, cost = ccost;
    }
};

std::vector<node> g[maxn];

void add(int u, int v, int joy, int cost) {
    g[u].push_back(node(v, joy, cost));
}

double d[maxn];
bool inqueue[maxn];
int cnt[maxn];

const int delta = 30;

bool spfa(double p) {
    for (int i = 0; i < maxn; i++) {
        d[i] = 1e9;
    }
    memset(inqueue, 0, sizeof(inqueue));
    memset(cnt, 0, sizeof(cnt));
    queue<int> q;
    q.push(0);
    d[0] = 0;
    cnt[0]++;
    inqueue[0] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inqueue[u] = false;
        if (cnt[u] > delta) {
            return true;
        }
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i].v;
            if (d[v] > d[u] + p * g[u][i].cost - g[u][i].joy) {
                d[v] = d[u] + p * g[u][i].cost - g[u][i].joy;
                if (!inqueue[v]) {
                    inqueue[v] = true;
                    q.push(v);
                    cnt[v]++;
                    if (cnt[v] > delta) {
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, joy, cost;
        cin >> u >> v >> joy >> cost;
        add(u, v, joy, cost);
    }
    for (int i = 1; i <= n; i++) {
        add(0, i, 0, 0);
    }
    double l = 0, r = 200.0;
    while (l + eps < r) {
        double mid = (l + r) / 2.0;
        if (spfa(mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }
    if (l == 0) {
        cout << -1 << endl;
    } else {
        cout << fixed << setprecision(1) << l << endl;
    }
    return 0;
}
————————

A method of completely using bare SPFA algorithm.

A score planning problem is actually the flexible application of the shortest path.

meaning of the title

There are many questions. In short:

\(n \) points and \ (m \) edges. Each edge has two attributes, namely cost \ (\ text {cost} \) and revenue \ (\ text {joy} \). Find a ring that maximizes the value of \ (\ dfrac {\ sum \ text {joy} {\ sum \ text {cost}} \) on the ring.

thinking

If we let the answer be \ (P \), then for any ring on the graph, there are:

Multiply the left and right sides of the inequality by \ (\ sum \ text {cost} \), then:

Change the position to get:

That is, when \ (P \) is the correct answer, there will be no negative ring on the graph.

For the \ (I \) edge, when running the SPFA algorithm, its actual edge weight should be

In addition, we can find that the problem requires the maximum value of a formula. Observe \ (P \ times \ sum \ text {cost} – \ sum \ text {joy} \) and find that this formula is monotonous. Then you can use dichotomy to reduce the number of calculations (from \ (200 \) to \ (\ log_2 (200) \ approx8 \)

Moreover, in this question, the question does not tell us the starting point. Therefore, we need to establish a super source point (point \ (0 \) in my code) and connect it with other \ (n \) points to an edge that will not affect the answer.

Finally, let me list some points that need attention:

  • The \ (\ text {D} \) array of SPFA needs to be of bool type, and cannot be assigned by memset, but must be assigned by for loop.
  • The left endpoint of bisection is initially set to \ (1 \), and the right endpoint is initially set to a number greater than or equal to \ (200 \).
  • When the left end point is equal to \ (0 \) after the dichotomy, it represents no solution and outputs \ (- 1 \).

You think it’s over? did not.

When you hand in the code written in the above idea, you will find that you only have 90 points.

According to the above idea, the only thing that can reduce the number of operation steps is within SPFA. We set a value \ (\ text {delta} \) to indicate that when a point has the upper limit of the number of times to join the team, we can score human flesh. It is found that when \ (\ text {delta} \) is equal to \ (10 \), we can pass this problem, and run fast, with a total of only 67ms, and successfully enter the first page of the optimal solution.

code

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<iomanip>
using namespace std;

const int maxn = 7010;
const double eps = 1e-3;

int n, m;

struct node {
    int v, joy, cost;
    node(int vv, int jjoy, int ccost) {
        v = vv, joy = jjoy, cost = ccost;
    }
};

std::vector<node> g[maxn];

void add(int u, int v, int joy, int cost) {
    g[u].push_back(node(v, joy, cost));
}

double d[maxn];
bool inqueue[maxn];
int cnt[maxn];

const int delta = 30;

bool spfa(double p) {
    for (int i = 0; i < maxn; i++) {
        d[i] = 1e9;
    }
    memset(inqueue, 0, sizeof(inqueue));
    memset(cnt, 0, sizeof(cnt));
    queue<int> q;
    q.push(0);
    d[0] = 0;
    cnt[0]++;
    inqueue[0] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inqueue[u] = false;
        if (cnt[u] > delta) {
            return true;
        }
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i].v;
            if (d[v] > d[u] + p * g[u][i].cost - g[u][i].joy) {
                d[v] = d[u] + p * g[u][i].cost - g[u][i].joy;
                if (!inqueue[v]) {
                    inqueue[v] = true;
                    q.push(v);
                    cnt[v]++;
                    if (cnt[v] > delta) {
                        return true;
                    }
                }
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, joy, cost;
        cin >> u >> v >> joy >> cost;
        add(u, v, joy, cost);
    }
    for (int i = 1; i <= n; i++) {
        add(0, i, 0, 0);
    }
    double l = 0, r = 200.0;
    while (l + eps < r) {
        double mid = (l + r) / 2.0;
        if (spfa(mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }
    if (l == 0) {
        cout << -1 << endl;
    } else {
        cout << fixed << setprecision(1) << l << endl;
    }
    return 0;
}