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}\)。为了方便计算，我们将个数取对数，可以将条件转化为：\(\sum\limits_{i=0}^k \log (\frac{wc_i}{a_i}) > 0\)，即：\(\sum\limits_{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("%.10f\n", l);
    return 0;
}