本文共 1863 字，大约阅读时间需要 6 分钟。

图论中的一个常见问题是检测是否存在负权环。负权环意味着从环中某一点出发，可以一直环绕下去，每次循环都获得正的权值，这在某些应用中是不允许的。为了检测这样的环，我们可以使用SPFA算法（队列优化的Bellman-Ford算法），它在图中寻找是否存在环的权重总和小于零。

在本文中，我们需要确定一个特定的L值，使得在某一精度下，满足ΣF[i]/ΣT[i] > L。通过移项和变形，我们可以将原式转换为ΣT[i] * L - ΣF[i] < 0。这意味着我们需要找到满足这个不等式的最小L值。

我们可以使用二分法来确定这个L值。二分法是一种高效的搜索算法，能够快速缩小可能的L值范围。具体来说，我们初始化L的范围，然后在每次迭代中计算中间值mid，并使用SPFA算法检查是否存在负权环。若检查结果为1，表示存在负权环，此时我们可以将L的上界调整为mid；否则，将L的下界调整为mid。

以下是实现这一过程的代码：

#include 
   
    #include 
    
     #include 
     
      using namespace std;struct asdf {    int to, zz, next;};int a[10001];int n, p, u, v, tt, F[10001], l[10001], cnt[10001];bool B[10001];double ll, r, mid, dis[10001];bool check(int d) {    queue
      
        Q;    for (int i = 1; i <= n; ++i) {        Q.push(i);        dis[i] = 0;        cnt[i] = 1;        B[i] = 1;    }    while (!Q.empty()) {        int h = Q.front();        Q.pop();        B[h] = 0;        for (int i = l[h]; i; i = a[i].next) {            if (dis[a[i].to] > dis[h] + d * a[i].zz - F[a[i].to]) {                dis[a[i].to] = dis[h] + d * a[i].zz - F[a[i].to];                if (B[a[i].to] == 0) {                    B[a[i].to] = 1;                    Q.push(a[i].to);                    if (++cnt[a[i].to] >= n) return 1;                }            }        }    }    return 0;}int main() {    scanf("%d%d", &n, &p);    for (int i = 1; i <= n; ++i) {        scanf("%d", &F[i]);    }    for (int i = 1; i <= p; ++i) {        scanf("%d%d%d", &u, &v, &tt);        a[++t] = (asdf){v, tt, l[u]};        l[u] = t;    }    ll = 0;    r = 100000;    while (r - ll > 0.0000001) {        mid = (ll + r) / 2;        if (check(mid) == 1) {            ll = mid;        } else {            r = mid - 0.0000001;        }    }    printf("%0.2lf", ll);}
      
     
    
   

通过上述代码，我们可以实现二分法结合SPFA算法来确定满足条件的最小L值。SPFA算法用于检测图中是否存在负权环，而二分法则用于高效地缩小L值的范围。这种方法不仅能够检测负权环，还能准确地找到满足ΣT[i] * L - ΣF[i] < 0的最小L值。