### 题意

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

### 思路

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

### 代码

#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;
}
for (int i = 1; i <= n; i++) {
}
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;
}
for (int i = 1; i <= n; i++) {
}
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;
}