#O1054. 缩点最长链

缩点最长链

题目描述

给定 nn 个点、mm 条有向边的图,每个点有点权 wi>0w_i > 0。把每个强连通分量缩成一个点(新点权为该分量内点权之和),得到一个有向无环图。求该 DAG 上一条路径的最大点权和(路径可以只含一个点)。

题目类型

强连通分量、缩点、DAG 上 DP

输入格式

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

第二行 nn 个整数 wiw_i。

接下来 mm 行,每行两个整数 u,vu, v。

输出格式

一行一个整数,表示最大点权和。

样例 #1

样例输入 #1

3 3
1 2 3
1 2
2 1
2 3

样例输出 #1

6

数据规模与约定

数据范围 说明
1≤n≤1051 \le n \le 10^5 点数
0≤m≤2×1050 \le m \le 2 \times 10^5 边数
1≤wi≤1061 \le w_i \le 10^6 点权
  • 缩点后按拓扑序 DP,答案用 long long。