#1983. 【模板】缩点 / 强连通分量

【模板】缩点 / 强连通分量

题目描述

给定一个 nn 个点 mm 条边有向图,每个点有一个权值,求一条路径,使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点,但是,重复经过的点,权值只计算一次。

输入格式

第一行两个正整数 n,mn,m。

第二行 nn 个整数,其中第 ii 个数 aia_i 表示点 ii 的点权。

第三至 m+2m+2 行,每行两个整数 u,vu,v,表示一条 u→vu\rightarrow v 的有向边。

输出格式

共一行,最大的点权之和。

样例

2 2
1 1
1 2
2 1
2

题目来源:洛谷 P3387