7788: 【模板题】缩点
[Creator : ]
Description
给定一个 $n$ 个点 $m$ 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
Input
第一行两个正整数 $n,m$
第二行 $n$ 个整数，其中第 $i$ 个数 $a_i$ 表示点 $i$ 的点权。
第三至 $m+2$ 行，每行两个整数 $u,v$，表示一条 $u\rightarrow v$ 的有向边。
第二行 $n$ 个整数，其中第 $i$ 个数 $a_i$ 表示点 $i$ 的点权。
第三至 $m+2$ 行，每行两个整数 $u,v$，表示一条 $u\rightarrow v$ 的有向边。
Output
共一行，最大的点权之和。
Constraints
对于 $100\%$ 的数据，$1\le n \le 10^4$，$1\le m \le 10^5$，$0\le a_i\le 10^3$。
Sample 1 Input
2 2
1 1
1 2
2 1
Sample 1 Output
2
原始结构
缩点后
缩点后
Sample 2 Input
9 10
1 1 1 1 1 6 7 8 9
1 2
2 3
2 5
3 4
4 3
4 7
5 1
5 4
6 4
8 9
Sample 2 Output
17
原始结构
缩点后
注意缩点后，新图中每个点按编号从小到大的顺序即为拓扑逆序。
如上图所示，有 $3$ 条路径。
其中权值最大为 $17$。
缩点后
注意缩点后，新图中每个点按编号从小到大的顺序即为拓扑逆序。
如上图所示，有 $3$ 条路径。
- $1 \to 2 \to 3$，路径权值总和为 $7+2+3=12$。
- $1 \to 2 \to 4$，路径权值总和为 $7+2+6=15$。
- $5 \to 6$，路径权值总和为 $9+8=17$。
其中权值最大为 $17$。