观光奶牛 spfa

spfa + 二分

题目
01分数规划
设 $ans$ 为 最大值
求: $$\frac{{\sum }_{i=1}^{k}f[i]}{{\sum }_{i=1}^{k}t[i]}\le ans$$
等价于: $$\sum _{i=1}^{k}f[i]?t[i]?ans\le 0$$
则: $$\sum _{i=1}^{k}t[i]?ans?f[i]\ge 0$$
二分ans 判负环是否存在
如果 存在，那么证明原式成立 范围缩小到 $[ans,r]$
如果 不存在， 那么证明原生不对 范围缩小到 $[l,ans]$

#include <bits/stdc++.h>
const int N = 1111, M = 1e4 + 111;
using namespace std;
int n, m, idx, h[N], v[N], cnt[N];
double f[N], d[N];
struct E {
    int v, n, w;
} g[M];
void add (int a, int b, int c) {
    g[idx].v = b; g[idx].n = h[a];g[idx].w = c; h[a] = idx ++;
}
bool spfa (double val) {
    queue<int> que;for (int i = 1; i <= n; ++ i)que.push(i), v[i] = 1, d[i] = cnt[i] = 0;while (que.size()) {
    auto t = que.front();que.pop();v[t] = 0;for (int i = h[t]; i; i = g[i].n) {
    int j = g[i].v;double w = g[i].w * val - f[t] + d[t];if (d[j] > w) {
    d[j] = w;cnt[j] = cnt[t] + 1;if (cnt[j] >= n) return true;if (!v[j]) que.push(j), v[j] = 1;}}}return false;
}
int main() {
    idx = 1;cin >> n >> m;for (int i = 1; i <= n; ++ i) cin >> f[i];for (int i = 1; i <= m; ++ i) {
    int a, b, c;cin >> a >> b >> c;add (a, b, c);}double l = 1, r = 1000;for (int i = 1; i <= 50; ++ i) {
    double mid = (l + r) / 2;if (spfa(mid)) l = mid;else r = mid;}printf ("%.2lf\n", l);return 0;
}