Coin Collector

题目描述

一个游戏有 $n$ 个房间和 $m$ 条隧道连通它们。每个房间都有一定数量的硬币。当你可以自由选择起始房间和结束房间并通过隧道移动时，你最多可以收集多少硬币？

输入格式

第一行输入两个整数 $n$ 和 $m$：房间数和隧道数。房间编号为 $1,2,\dots,n$。 接着，有 $n$ 个整数 $k_1,k_2,\ldots,k_n$：每个房间的硬币数。 最后，有 $m$ 行描述隧道。每行有两个整数 $a$ 和 $b$：存在一条从房间 $a$ 到房间 $b$ 的隧道。每条隧道是单向的。

输出格式

输出一个整数：你最多可以收集的硬币数。

4 4
4 5 2 7
1 2
2 1
1 3
2 4

16

提示

$1 \le n \le 10^5$ $1 \le m \le 2 \cdot 10^5$ $1 \le k_i \le 10^9$ $1 \le a,b \le n$

标签: CSES1686|图论

来源

CSES1686|图论