题目传送门(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$

由于$i$与$i+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);}