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实现
代码
#include<cstring>
#include<queue>
#include<cstdio>
#include<algorithm>
#define rd read()
#define rep(i,a,b) for(register int i = (a); i <= (b); ++i)
#define per(i,a,b) for(register int i = (a); i >= (b); --i)
using namespace std; const int N = 1e3 + ;
const int M = 5e3 + ;
const int inf = ~0U >> ;
const double eps = 1e-; int n, m;
int head[N], tot, a[N], cnt[N], vis[N];
int head2[N], tot2;
double f[N]; queue<int> q; int read() {
int X = , p = ; char c = getchar();
for(; c > '' || c < ''; c = getchar()) if(c == '-') p = -;
for(; c >= '' && c <= ''; c = getchar()) X = X * + c - '';
return X * p;
} struct edge {
int fr, nxt, to;
double val;
}e[M << ], E[M << ]; void add(int u, int v, double val) {
e[++tot].to = v;
e[tot].val = val;
e[tot].nxt = head[u];
e[tot].fr = u;
head[u] = tot;
} void add2(int u, int v, double val) {
E[++tot2].to = v;
E[tot2].val = val;
E[tot2].nxt = head2[u];
E[tot2].fr = u;
head2[u] = tot2;
} int ch(int x) {
return ((x + ) ^ ) - ;
} int spfa() {
f[] = ;
q.push();
for(int u; !q.empty();) {
u = q.front(); q.pop();
vis[u] = ;
for(int i = head2[u]; i; i = E[i].nxt) {
int nt = E[i].to;
double upd = f[u] + E[i].val;
if(f[nt] + eps < upd) continue;
cnt[nt] = cnt[u] + ;
if(cnt[nt] >= n) return ;
f[nt] = f[u] + E[i].val;
if(!vis[nt]) {vis[nt] = ; q.push(nt);}
}
}
return ;
} int check(double x) {
memset(head2, , sizeof(head2));
memset(cnt, , sizeof(cnt));
rep(i, , n) f[i] = inf;
tot2 = ;
rep(i, , tot) {
int u = e[i].fr, v = e[i].to;
double val = x * e[i].val - a[u];
add2(u, v, val);
}
return spfa();
} int main()
{
n = rd; m = rd;
rep(i, , n) a[i] = rd;
rep(i, , m) {
int u = rd, v = rd, val = rd;
add(u, v, val);
}
double l = , r = , mid, ans = ;
while(l + eps < r) {
mid = (l + r) / ;
if(check(mid)) ans = mid, l = mid;
else r = mid;
}
printf("%.2lf\n", ans);
}