题目传送门(BZOJ)
>原文链接<

题解 :

分数规划题,二分答案。

考虑某答案ans,它可行当且仅当有一环ans \ge (\sum\limits_{i=1}^{cnt}dis[i][i+1])\div cnt 其中cnt是环上点的个数

移项ans\times cnt \ge \sum\limits_{i=1}^{cnt}dis[i][i+1] 其中ans的数量恰好等于dis的数量,都是cnt

那么就变成了\sum\limits_{i=1}^{cnt}(dis[i][i+1]-ans) \le 0

由于ii+1是由某条边直接相连的,所以我们可以把所有边都减掉ans

这样,如果有某个答案符合条件,\sum\limits_{i=1}^{cnt}dis[i][i+1] \le 0 ,就是有一个负环。

如果二分某个答案有负环,那么这个答案就可行,而且可以更小,把r调成mid,否则就太大了,把l调成mid

为了防止精度出问题,我采取迭代T = 60 次的方法,在这道题上表现良好

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define f2 double#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)const int N = 3100, M = 11000;struct Edge { int to; f2 val; Edge *next;}*h[N],e[M];int _, n, m;int ra[M], rb[M];f2 rv[M];inline void Add_Edge(int u, int v, f2 w) { Edge *tmp = &e[++_]; tmp->to = v; tmp->val = w; tmp->next = h[u]; h[u] = tmp;}inline void build(f2 mid) { _ = 0; memset(h, 0, sizeof h); for(int i = 1; i <= m; i ++ ) { Add_Edge(ra[i], rb[i], rv[i]-mid); }}bool flag, tag[N];f2 dis[N];void spfa(int p) { tag[p] = 1; rev(i, p) if(dis[i->to] > dis[p]+i->val) { if(tag[i->to]) { flag = 1; break; } dis[i->to] = dis[p]+i->val; spfa(i->to); } tag[p] = 0;}inline bool check() { memset(dis, 0, sizeof dis); memset(tag, 0, sizeof tag); flag = 0; for(int i = 1; i <= n; i ++ ) { spfa(i); if(flag) return 1; } return 0;}int main() { scanf("%d%d", &n, &m); for(int i = 1; i <= m; i ++ ) { scanf("%d%d%lf", &ra[i], &rb[i], &rv[i]); } f2 l = -1e9, r = 1e9; int T = 60; while(T -- ) { f2 mid = (l+r)/2; build(mid); if(check()) r = mid; else l = mid; } printf("%.8f\n", l);}