Description
作为对奶牛们辛勤工作的回报，Farmer John决定带她们去附近的大城市玩一天。旅行的前夜，奶牛们在兴奋地
讨论如何最好地享受这难得的闲暇。 很幸运地，奶牛们找到了一张详细的城市地图，上面标注了城市中所有
L(2 <= L <= 1000)座标志性建筑物（建筑物按1..L顺次编号），以及连接这些建筑物的P(2 <= P <= 5000)条道路
。按照计划，那天早上Farmer John会开车将奶牛们送到某个她们指定的建筑物旁边，等奶牛们完成她们的整个
旅行并回到出发点后，将她们接回农场。由于大城市中总是寸土寸金，所有的道路都很窄，政府不得不把它们都
设定为通行方向固定的单行道。 尽管参观那些标志性建筑物的确很有意思，但如果你认为奶牛们同样享受穿行于
大城市的车流中的话，你就大错特错了。与参观景点相反，奶牛们把走路定义为无趣且令她们厌烦的活动。对于
编号为i的标志性建筑物，奶牛们清楚地知道参观它能给自己带来的乐趣值F_i (1 <= F_i <= 1000)。相对于奶牛们
在走路上花的时间，她们参观建筑物的耗时可以忽略不计。 奶牛们同样仔细地研究过城市中的道路。她们知道
第i条道路两端的建筑物 L1_i和L2_i（道路方向为L1_i -> L2_i），以及她们从道路的一头走到另一头所需要的
时间T_i(1 <= T_i <= 1000)。 为了最好地享受她们的休息日，奶牛们希望她们在一整天中平均每单位时间内获得
的乐趣值最大。当然咯，奶牛们不会愿意把同一个建筑物参观两遍，也就是说，虽然她们可以两次经过同一个建筑
物，但她们的乐趣值只会增加一次。顺便说一句，为了让奶牛们得到一些锻炼，Farmer John要求奶牛们参观至少2个
建筑物。 请你写个程序，帮奶牛们计算一下她们能得到的最大平均乐趣值。
solution
二分答案$mid$
记环上的边$e(u, v)$和点$ u $为,则$tmp = sum u / sum e$， 化为 $tmp * sum e - sum u = 0$
如果$mid < tmp$, 则 $mid * sum e - sum u < 0$， 然后把 $l$ 记为$mid$继续二分， 不然就把 $r$ 记为$mid$ 继续二分
因为要使答案尽可能大， 所以我们希望找出一个环使得 $mid * sum e - sum u < 0$。
那么我们就可以在每次check时 构造一个新图， 每条边的权值为 $mid * e - u$。 然后找到一个负环即可check。
找负环用spfa实现
代码
1 #include<cstring> 2 #include<queue> 3 #include<cstdio> 4 #include<algorithm> 5 #define rd read() 6 #define rep(i,a,b) for(register int i = (a); i <= (b); ++i) 7 #define per(i,a,b) for(register int i = (a); i >= (b); --i) 8 using namespace std; 9 10 const int N = 1e3 + 5; 11 const int M = 5e3 + 5; 12 const int inf = ~0U >> 1; 13 const double eps = 1e-6; 14 15 int n, m; 16 int head[N], tot, a[N], cnt[N], vis[N]; 17 int head2[N], tot2; 18 double f[N]; 19 20 queue<int> q; 21 22 int read() { 23 int X = 0, p = 1; char c = getchar(); 24 for(; c > '9' || c < '0'; c = getchar()) if(c == '-') p = -1; 25 for(; c >= '0' && c <= '9'; c = getchar()) X = X * 10 + c - '0'; 26 return X * p; 27 } 28 29 struct edge { 30 int fr, nxt, to; 31 double val; 32 }e[M << 1], E[M << 1]; 33 34 void add(int u, int v, double val) { 35 e[++tot].to = v; 36 e[tot].val = val; 37 e[tot].nxt = head[u]; 38 e[tot].fr = u; 39 head[u] = tot; 40 } 41 42 void add2(int u, int v, double val) { 43 E[++tot2].to = v; 44 E[tot2].val = val; 45 E[tot2].nxt = head2[u]; 46 E[tot2].fr = u; 47 head2[u] = tot2; 48 } 49 50 int ch(int x) { 51 return ((x + 1) ^ 1) - 1; 52 } 53 54 int spfa() { 55 f[1] = 0; 56 q.push(1); 57 for(int u; !q.empty();) { 58 u = q.front(); q.pop(); 59 vis[u] = 0; 60 for(int i = head2[u]; i; i = E[i].nxt) { 61 int nt = E[i].to; 62 double upd = f[u] + E[i].val; 63 if(f[nt] + eps < upd) continue; 64 cnt[nt] = cnt[u] + 1; 65 if(cnt[nt] >= n) return 1; 66 f[nt] = f[u] + E[i].val; 67 if(!vis[nt]) {vis[nt] = 1; q.push(nt);} 68 } 69 } 70 return 0; 71 } 72 73 int check(double x) { 74 memset(head2, 0, sizeof(head2)); 75 memset(cnt, 0, sizeof(cnt)); 76 rep(i, 0, n) f[i] = inf; 77 tot2 = 0; 78 rep(i, 1, tot) { 79 int u = e[i].fr, v = e[i].to; 80 double val = x * e[i].val - a[u]; 81 add2(u, v, val); 82 } 83 return spfa(); 84 } 85 86 int main() 87 { 88 n = rd; m = rd; 89 rep(i, 1, n) a[i] = rd; 90 rep(i, 1, m) { 91 int u = rd, v = rd, val = rd; 92 add(u, v, val); 93 } 94 double l = 0, r = 1005, mid, ans = 0; 95 while(l + eps < r) { 96 mid = (l + r) / 2; 97 if(check(mid)) ans = mid, l = mid; 98 else r = mid; 99 } 100 printf("%.2lf ", ans); 101 }