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 = 0, fh = 1; char ch; for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1; for (; isdigit(ch); ch = getchar()) x = (x<<1) + (x<<3) + (ch^'0'); return x * fh; } #include <stack> const int N = 1e4+1e2, M = 1e5*2+1e2; //点的范围和边的范围 开大点防止数据bug struct edge { int to[M], Next[M], Head[N], e; void init() {Set(Head, 0); e = 0;} }; //用链式前向星存边，访问更加迅速 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 = 0, scc_cnt = 0; 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 = 0; //答案 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, 1, n) val[i] = read(); while (m--) { int u = read(), v = read(); add_edge (u, v, G1); //把边加入G1中 } For (i, 1, n) if (!pre[i]) Tarjan (i); //搜索强联通 For (i, 1, 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, 1, scc_cnt) if (!in_deg[i]) dfs(i); //搜索入度为0的点 printf ("%d ", max_ans); }