30131 - Sightseing Cows

讨论

统计

通过次数

提交次数

旧版界面

时间限制 : 1 秒

内存限制 : 128 MB

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

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

输出这个最大值。

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

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

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

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

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

6.00