链接: https://cses.fi/problemset/task/1686

板块: Graph Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

一个游戏有 $n$ 个房间和它们之间的 $m$ 条隧道。每个房间有一定数量的硬币。在隧道中移动时，你可以自由选择起点和终点房间，最多能收集多少硬币？

输入

第一行输入包含两个整数 $n$ 和 $m$：房间数量和隧道数量。房间编号为 $1,2,\dots,n$。

接着有 $n$ 个整数 $k_1,k_2,\ldots,k_n$：每个房间中的硬币数量。

最后有 $m$ 行描述隧道。每行包含两个整数 $a$ 和 $b$：存在一条从房间 $a$ 到房间 $b$ 的隧道。每条隧道都是单向隧道。

输出

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

数据范围

$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$

样例输入

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

样例输出

16