PS：这个题数据是由Hany01大大出出来的 %%%
这个题显然是一道强联通+DAGdp的题 （题目背景有= =）
缩点的原因就是：不缩会一直在一个地方绕圈圈 而且不能进行后面的DAPdp 而且给你的所有点权全是正的
我在这用的是Tarjan（因为他发明算法太多了233）
这个dp方程比较容易找 令dp[u] 表示 缩点后 第u个强联通分量为起点的路径上点和的最大值
所以有 dp[u] = max{dp[v]} + val[u] （这里v是指u出发可以到达的点）
由于是DAGdp 所以我们一开始要从入度为0的点出发 一直向下走 回溯的时候更改这个节点的dp值
下附程序（Tarjan讲解见程序）：
#include <bits/stdc++.h>
#define For(i, l, r) for(int i = (l); i <= (int)(r); ++i)
#define Fordown(i, r, l) for(int i = (r); i >= (int)(l); --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std; inline int read() {
int x = , fh = ; char ch;
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -;
for (; isdigit(ch); ch = getchar()) x = (x<<) + (x<<) + (ch^'');
return x * fh;
} #include <stack>
const int N = 1e4+1e2, M = 1e5*+1e2; //点的范围和边的范围 开大点防止数据bug
struct edge {
int to[M], Next[M], Head[N], e;
void init() {Set(Head, ); e = ;}
}; //用链式前向星存边，访问更加迅速
edge G1, G2; //结构体便于多图 void add_edge (int u, int v, edge &G) { //引用G为了更新G
G.to[++G.e] = v;
G.Next[G.e] = G.Head[u];
G.Head[u] = G.e;
} //加入一条有向边 #define Travel(i, u, G) for(int i = G.Head[u]; i; i = G.Next[i])
//链式前向星的遍历方式 i表示在G图中，所有从u出发的边 （宏定义偷懒233）
int pre[N], lowlink[N], sccno[N], dfs_clock = , scc_cnt = ;
stack<int> S;
//Tarjan所需要的一些变量，时间戳dfs_clock，最早进入时间pre，能访问最远祖先lowlink
//强联通分量总数scc_cnt，每个点所属强联通分量编号sccno
int val[N], val1[N];
//val表示原图中的权值，val1表示缩点后每个强联通分量的权值
void Tarjan (int u) { //Tarjan主体（访问u）
pre[u] = lowlink[u] = ++dfs_clock; //第一次进入 把时间和最远到达祖先设为u
S.push(u); //把u放入栈中
Travel (i, u, G1) { //遍历原图从u开始的节点
int v = G1.to[i]; //取出到达的节点
if (!pre[v]) { //没有访问过
Tarjan (v); //递归向下继续搜
lowlink[u] = min(lowlink[u], lowlink[v]); //更新能到达最远祖先的值
} else if (!sccno[v]) //不是别的强联通分量中的点 且 已经访问过了(也就是存在了一条返祖边）
lowlink[u] = min(lowlink[u], pre[v]); //更新最远祖先（因为v在u之前被访问）证明有环
}
if (lowlink[u] == pre[u]) { //能到达的最远祖先就是自己
++scc_cnt; //将总数增加
for(;;) { //不断递归
int now = S.top(); S.pop(); //取出当前栈顶的数
sccno[now] = scc_cnt; //标记点的编号
val1[scc_cnt] += val[now]; //统计强联通分量的权值
if (now == u) break; //到了自己就停下来 不可能继续向上走了
}
}
} int in_deg[N]; //记录入度
int max_ans = ; //答案
int dp[N]; //dp数组
bool vis[N]; //标记是否到达
void dfs(int u) {
if (vis[u]) return;
vis[u] = true; //似乎不要也行 但好像更慢
dp[u] = val1[u]; //初始化标记为强联通得权值
Travel (i, u, G2) { //从缩点后的图开始遍历
int v = G2.to[i]; //取出到达点
dfs(v); //向下遍历
dp[u] = max(dp[u], dp[v] + val1[u]); //回溯时更新dp值
}
max_ans = max(max_ans, dp[u]); //更新答案
} int main() {
int n = read(), m = read();
G1.init(); G2.init();
For (i, , n)
val[i] = read();
while (m--) {
int u = read(), v = read();
add_edge (u, v, G1); //把边加入G1中
}
For (i, , n)
if (!pre[i]) Tarjan (i); //搜索强联通 For (i, , n)
Travel (j, i, G1) { //遍历所有的边
int v = G1.to[j];
if (sccno[i] == sccno[v]) continue; //如果在同一个强联通分量中就向下走
add_edge (sccno[i], sccno[v], G2); //把新边加入G2中
++in_deg[sccno[v]]; //增加v入度
} For (i, , scc_cnt)
if (!in_deg[i]) dfs(i); //搜索入度为0的点
printf ("%d\n", max_ans);
}