#O1054. 缩点最长链
缩点最长链
题目描述
给定 个点、 条有向边的图,每个点有点权 。把每个强连通分量缩成一个点(新点权为该分量内点权之和),得到一个有向无环图。求该 DAG 上一条路径的最大点权和(路径可以只含一个点)。
题目类型
强连通分量、缩点、DAG 上 DP
输入格式
第一行两个整数 。
第二行 个整数 。
接下来 行,每行两个整数 。
输出格式
一行一个整数,表示最大点权和。
样例 #1
样例输入 #1
3 3
1 2 3
1 2
2 1
2 3
样例输出 #1
6
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 点数 | |
| 边数 | |
| 点权 |
- 缩点后按拓扑序 DP,答案用
long long。