“蔚来杯“2022牛客暑期多校训练营2 D.[Link with Game Glitch] 二分答案+SPFA判环

D.Link with Game Glitch

题目分析

有$m$个配方，每个配方可以使用$k\times a_i$个$b_i$种原料生成$k\times c_i$个$d_i$种原料。现在要求在$k$上乘一个权值$w$，使得所有配方间不存在可以循环生成无限物品的局面。要求最大化$m$。

显然要生成无限物品，需要存在一个环且沿该环生成一轮得到的物品数目比原来更多，即为环上满足所有的边有$k(c[i]-a[i])>0$即为$k\frac{c[i]}{a[i]}>1$。

由于可能存在多个环，我们只需要保证最大环不会循环生成即可。显然可以二分答案来做。

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;
}