"Wei Lai Cup" 2022 Niuke summer multi school training camp 2 d.[link with game glitch] two point answer +spfa ring

D.Link with Game Glitch

Topic analysis

Yes $m$ A recipe , Each recipe can be used $k\times a_i$ individual $b_i$ Raw material generation $k\times c_i$ individual $d_i$ Grow raw materials . Now the request is $k$ Multiply by a weight $w$, So that there is no situation that infinite items can be generated circularly among all recipes . Demand maximum $m$.

Obviously, it is necessary to generate infinite items , There needs to be a ring and the number of items generated along the ring is more than the original , That is, all edges on the ring have $k(c[i]-a[i])>0$ That is to say $k\frac{c[i]}{a[i]}>1$.

Since there may be multiple rings , We just need to ensure that the maximum ring will not be generated circularly . Obviously, you can do it with two answers .

Code

#include <bits/stdc++.h>
//#pragma gcc optimize(2)
#define double long double
#define endl '\n'
using namespace std;

const int N = 2e3 + 10, MOD = 1e9 + 7;
const double EPS = 1e-8;

struct node{
     int v; double w; };

vector<node> g[N];
int n, m, cnt[N];
double dis[N];
bitset<N> vis;

bool check(double x){
    
    queue<int> q;
    x = -log(x);
    vis.set();
    memset(dis, 0, sizeof(dis));
    memset(cnt, 0, sizeof(cnt));
    for(int i = 1; i <= n; i++) q.emplace(i);
    while(q.size()){
    
        int u = q.front(); q.pop();
        vis.reset(u);
        for(auto nxt : g[u]){
    
            int v = nxt.v;
            double w = nxt.w;
            if(dis[v] > dis[u] + w + x){
    
                dis[v] = dis[u] + w + x;
                cnt[v] = cnt[u] + 1;
                if(cnt[v] > n) return true;
                if(!vis[v]){
    
                    q.emplace(v);
                    vis.set(v);
                }
            }
        }
    }
    return false;
}   

inline void solve(){
    
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
    
        int a, b, c, d; cin >> a >> b >> c >> d;
        g[b].emplace_back(node{
    d, -log((1.0 * c) / a)});
    }
    double l = 0, r = 1;
    for(int i = 1; i <= 300; i++){
    
        double mid = (l + r) / 2;
        if(check(mid)) r = mid;
        else l = mid;
    }
    cout << l << endl;
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}