跳转至

牛客多校2 D

题目链接

题目大意

给出\(n\)个食材，\(m\)个食谱，为防止无限创造食物，使食谱的产出乘以系数\(w\)，问最大的\(w\)

题解

最大最小考虑二分，现在目标是求出check函数，想要使食物不被无限制造，问题等价于食谱图中不存在边权乘积大于1的环，但这样写check函数免不了会爆double，我们考虑转换，将边权都取log的话问题似乎更简单了，转化成了食谱图中不存在正环，套用spfa判正环模板即可

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
using namespace std;
const int N = 2005;
const double eps = 1e-8;
int head[N], e[N], ne[N], idx = 0;
int f[N];
double dis[N];
double w[N];
bool vis[N];
int n, m;
queue<int> q;
void add(int a, int b, double c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = head[a];
    head[a] = idx ++ ;
}
bool check(double x) {
    memset(vis, false, sizeof(vis));
    memset(f, 0, sizeof(f));
    while(q.size()) q.pop();
    for(int i = 1; i <= n ; i ++ ) {
        vis[i] = true;
        dis[i] = 0;
        q.push(i);
    }
    while(q.size()) {
        int pos = q.front();
        q.pop();
        vis[pos] = false;
        for(int i = head[pos]; i != -1; i = ne[i]) {
            int j = e[i];
            if(dis[j] < dis[pos] + w[i] + x) {
                dis[j] = dis[pos] + w[i] + x;
                f[j] = f[pos] + 1;
                if(f[j] >= n) return false;
                if(!vis[j]) {
                    q.push(j);
                    vis[j] = true;
                }
            }    
        }
    }
    return true;
}
int main() {
    cin >> n >> m;
    memset(head, -1, sizeof(head));
    for(int i = 1; i <= m; i ++ ) {
        int a, b;
        double x, y;
        cin >> x >> a >> y >> b;
        add(a, b, log(y * 1.0 / x));
    }

    double l = 0, r = 1.0;
    while(l < r - eps) {
        double mid = (l + r) / 2.0;
        if(check(log(mid)))l = mid;
        else r = mid;
    }
    printf("%.8lf", l);
    return 0;
}