思路
模板题，先使用 (Tarjan) 进行缩点，然后重新建边，最后拓扑排序即可
Tarjan
强连通分量
在有向图G<V,E>中，对于点集V'∈V, 点集中的任意两点都可达，则称V'为强连通
Tarjan
在有向图中，(DFS) 时，我们需要维护 (dfn) 和 (low)，目的在于把所有的强连通分量缩成一个点(因为题目里说可以重复走，而强连通分量里两点都可以到达)
设 (dfn_i) 为遍历到当前节点 (i) 的时间戳，(low_i) 为当前节点 (i) 能回溯到的最早节点，
当 (dfn_i = low_i) 时说明以 (i) 为根形成了强连通分量，
此时我们可以用栈来维护当前强连通分量里的所有点。
拓扑排序
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。
此时缩点后的图是一个有向无环图(强连通分量被缩成点)，我们考虑使用拓扑排序求出最终的最长路径
先将入度为 (0) 的点进入队列，然后出队，将可到达的点的入度减 (1) ，然后将当前入度为 (0) 点加入队列，过程中可以 (DP) 求出最长路径
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 1e4 + 10;
const int MAXM = 1e5 + 10;
queue <int > s;
int sta[MAXN] ,ind = 0;
vector <int > c[MAXN];
int in[MAXN];
struct node {
int next, to ,from;
}edge[MAXM];
int head[MAXN] ,cnt = 0;
void add (int from ,int to) {
edge[++ cnt].next = head[from];
head[from] = cnt;
edge[cnt].to = to;
edge[cnt].from = from;
}
int n ,m ,answ = 0;
int dis[MAXN] ,dis_[MAXN];
int tot = 0 ,times = 0;
int dfn[MAXN] ,low[MAXN] ,ins[MAXN] = {0} ,vis[MAXN];
void tarjan (int u) {
dfn[u] = low[u] = ++ times;//初始dfn和low均为时间戳
sta[++ ind] = u ,ins[u] = 1;//进栈，手写
for (int q = head[u];~ q;q = edge[q].next) {//dfs
int v = edge[q].to;
if (! dfn[v]) {//向下遍历
tarjan (v);
low[u] = min (low[u] ,low[v]);
}
else if (ins[v])
low[u] = min (low[u] ,dfn[v]);
}
if (low[u] == dfn[u]) {//找到强连通分量
tot ++;//当前强连通分量 的 新的节点编号(因为缩成一个点了)
while (true) {
vis[sta[ind]] = tot;
dis_[tot] += dis[sta[ind]];//将路径长度累加到点上
ins[sta[ind]] = 0; ind --;//出栈
if (u == sta[ind + 1])//当前到根，退出
break;
}
}
}
int tot_ = 0;
int dp[MAXN];
void toposort () {
for (int q = 1;q <= tot;++ q) {//预处理入度为0的节点
if (in[q] == 0) {
s.push(q);
dp[q] = dis_[q];
}
}
while (! s.empty()) {
int u = s.front();
s.pop();
for (int q = 0;q < c[u].size();++ q) {//向下遍历
int v = c[u][q];
in[v] --;//减去1
dp[v] = max (dp[v] ,dp[u] + dis_[v]);//DP求出最长路
if (in[v] == 0) {//将当前入度为0的节点进队
s.push(v);
answ = max (answ ,dp[v]);
}
}
}
}
int main () {
memset (head ,-1 ,sizeof (head));
memset (in ,0 ,sizeof (in));
scanf ("%d%d",&n ,&m);
for (int q = 1;q <= n;++ q)
scanf ("%d",dis + q);
int from_ ,to_;
for (int q = 1;q <= m;++ q) {//初始边，此处链式前向星
scanf ("%d%d",&from_ ,&to_);
add (from_ ,to_);
}
for (int q = 1;q <= n;++ q)//tarjan
if (! dfn[q]) tarjan (q);
for (int q = 1;q <= m;++ q) {//重新建边(缩点后) ，此处用邻接表
if (vis[edge[q].from] != vis[edge[q].to]) {
from_ = vis[edge[q].from] ,to_ = vis[edge[q].to];
c[from_].push_back(to_);
in[to_] ++;
}
}
toposort ();//拓扑排序
for (int q = 1;q <= tot;++ q)
answ = max (answ ,dp[q]);
printf ("%d
",answ);
return 0;
}