Link with Game Glitch（负环）

题意

有(n)个物品，(m)个转换，每(ka_i)个(b_i)类物品可以换(w cdot kc_i)个(d_i)类物品。其中(k)为任意正实数。

求最大的(0 leq w leq 1)使得不存在一种转换方式可以得到无限多的某类物品。

题目保证当(w = 1)时，必然存在一种转换方式使得某类物品可以得到无限多个。

（题目翻译来源于emofunc的讲解PPT）

题目链接：https://ac.nowcoder.com/acm/contest/33187/D

数据范围

(2 leq n leq 1000)
(2 leq m leq 2000)

思路

由于(k)为任意正实数，因此我们可以计算每个(b_i)可以换多少个(d_i)，答案是(frac{w cdot c_i}{a_i})。

然后我们再考虑什么情况下某类物品可以得到无限多个，不妨设该类物品为(p_0)，且初始数量为(1)。使用(p_0)换取若干(p_1)，然后(p_1)再换取若干(p_2)，依此类推，最终(p_{k-1})换取若干(p_k)，(p_k)再换取若干(p_0)。如果一轮循环之后的(p_0)个数大于(1)，则最终(p_0)可以无限获得。

一轮循环之后的(p_0)个数为(frac{wc_1}{a_1} cdot frac{wc_2}{a_2} cdots frac{wc_k}{a_k} cdot frac{wc_0}{a_0})。为了方便计算，我们将个数取对数，可以将条件转化为：(sumlimits_{i=0}^k log (frac{wc_i}{a_i}) > 0)，即：(sumlimits_{i=0}^k -log (frac{wc_i}{a_i}) < 0)。

因此，我们在(b_i)与(d_i)之间连一条权值为(-log(frac{c_i}{a_i}))的有向边。然后二分(w)。最后使用spfa算法判断图中是否存在负环即可。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

const int N = 2010;
const double eps = 1e-8;

int n, m;
int h[N], e[N], ne[N], idx;
double w[N], d[N];
bool st[N];
int cnt[N];

void add(int a, int b, double c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

bool check(double x)
{
    queue<int> que;
    for(int i = 1; i <= n; i ++) {
        que.push(i);
        st[i] = true;
        cnt[i] = 0;
        d[i] = 0;
    }
    double k = log(x);
    while(que.size()) {
        int t = que.front();
        que.pop();
        st[t] = false;
        for(int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if(d[j] > d[t] - w[i] - k) {
                d[j] = d[t] - w[i] - k;
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= n) return false;
                if(!st[j]) {
                    st[j] = true;
                    que.push(j);
                }
            }
        }
    }
    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i ++) {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        add(b, d, log(1.0 * c / a));
    }
    double l = 0.0, r = 1.0;
    for(int i = 0; i < 100; i ++) {
        double mid = (l + r) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    }
    printf("%.10fn", l);
    return 0;
}