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

D.Link with Game Glitch 题目分析

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

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

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

Code

#include 
//#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 g[N];
int n, m, cnt[N];
double dis[N];
bitset vis;

bool check(double x){
    queue q;
    x = -log(x);
    vis.set();
    memset(dis, 0, sizeof(dis));
    memset(cnt, 0, sizeof(cnt));
    for(int i = 1; i  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 > 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