给定一张 N N N 个点、 M M M 条边的有向图，每个点都有一个权值 p i p_i pi，每条边都有一个权值 w i w_i wi。
求图中的一个环，使“环上各点的权值之和”除以“环上各边的权值之和”最大。
输出这个最大值。
留意：数据保证至少存在一个环。
输入格式
第一行包罗两个整数 N N N 和 M M M。
接下来 N N N 行每行一个整数，表示 p i p_i pi。
再接下来 M M M 行，每行三个整数 a a a， b b b， w [ i ] w w，表示点 a a a 和 b b b 之间存在一条边，边的权值为 w i w_i wi。
输出格式
输出一个数表示结果，生存两位小数。
样例 #1
样例输入 #1
5 7
30
10
10
5
10
1 2 3
2 3 2
3 4 5
3 5 2
4 5 5
5 1 3
5 2 2
复制代码
样例输出 #1
6.00
复制代码
提示
【数据范围】
2 ≤ N ≤ 1000 2≤N≤1000 2≤N≤1000,
2 ≤ M ≤ 5000 2≤M≤5000 2≤M≤5000,
1 ≤ p i , w i ≤ 1000 1≤p_i,w_i≤1000 1≤pi,wi≤1000
算法思想
根据题目描述，求的是图中的一个环，使“环上各点的权值之和”除以“环上各边的权值之和”最大，不妨设即环上各点的权值之和为 ∑ p i \sum p_i ∑pi，各边的权值之和为 ∑ w i \sum w_i ∑wi，即求 ∑ p i ∑ w i \frac{\sum p_i}{\sum w_i} ∑wi∑pi的最大值。这种办理“最优比率” 的问题，可以利用「01分数规划」。
01分数规划 ：01指取还是不取，分数即所求型式为 a b \frac{a}{b} ba，规划就是选取最好的方案。
01分数规划一般接纳二分答案的方式求解。对于本题来说，即求是否存在 m i d mid mid，使环上各点的权值之和除以环上各边的权值之和大于 m i d mid mid，即 ∑ p i ∑ w i > m i d \frac{\sum p_i}{\sum w_i}>mid ∑wi∑pi>mid，进一步整理可得： ∑ p i − m i d × ∑ w i > 0 \sum p_i-mid\times \sum w_i>0 ∑pi−mid×∑wi>0
其中， p i p_i pi表示节点 i i i的权值，为了方便处理，可以将节点的边权累加到该节点的出边上，那么不等式可以进一步变化为：
∑ ( p i − m i d × w i ) > 0 \sum ({p_i-mid\times w_i})>0 ∑(pi−mid×wi)>0
那么，要判断在包罗环的图中是否存在 m i d mid mid，使环上各点的权值之和除以环上各边的权值之和大于 m i d mid mid，就等价于判断当图中边权为 p i − m i d × w i {p_i-mid\times w_i} pi−mid×wi时，是否存在正权环。
而判断是否存在正权环可以利用「SFPA」算法，基本思想与判断负环稍有不同。判断负环可以参考博主的另一篇文章：每周一算法：负环判断。判断正权环时：
要求最长路，即 d [ v ] < d [ u ] + w d[v] < d + w d[v]<d+w时，更新 v v v点到出发点的最长路；
当 v v v点到出发点的最长路被更新时，累加最长路中包罗的边数，即 c n t [ v ] = c n t [ u ] + 1 cnt[v]=cnt+1 cnt[v]=cnt+1
如果边数 c n t [ v ] > = n cnt[v]>=n cnt[v]>=n，说明图中存在正权环。
算法实现
综合上述，求 ∑ p i ∑ w i \frac{\sum p_i}{\sum w_i} ∑wi∑pi的最大值算法实现如下：
在 [ L , R ] [L,R] [L,R]范围内通过二分查找答案，对于中间结果 m i d mid mid：
利用SPFA算法判断当边权为 p i − m i d × w i p_i-mid\times w_i pi−mid×wi时，图中是否存在正权环
如果存在正权环，则在 [ m i d , R ] [mid,R] [mid,R]范围继续查找答案
否则不存在正权环，则在 [ L , m i d ] [L,mid] [L,mid]范围继续查找答案
时间复杂度
本题中的01分数规划在二分答案的过程中，必要用SPFA算法判断正权环，时间复杂度为 O ( k M l o g W ) O(kMlogW) O(kMlogW)，其中 k k k是常数， M M M为边数， W W W为边权之和。
代码实现