#192. 「Sightseeing Cows」 观光奶牛

「Sightseeing Cows」 观光奶牛

给定一张L个点、P条边的有向图,每个点都有一个权值f[i],每条边都有一个权值t[i]。

求图中的一个环,使“环上各点的权值之和”除以“环上各边的权值之和”最大。

输出这个最大值。

注意:数据保证至少存在一个环。

输入格式

第一行包含两个整数L和P。

接下来L行每行一个整数,表示f[i]。

再接下来P行,每行三个整数a,b,t[i],表示点a和b之间存在一条边,边的权值为t[i]。

输出格式

输出一个数表示结果,保留两位小数。

数据范围

2L10002 \le L \le 1000,
2P50002 \le P \le 5000,
1 \le f\[i\],t\[i\] \le 1000

输入样例:

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

输出样例:

6.00

来源

  • 《算法竞赛进阶指南》
  • acwing 可能含有视频讲解