我美好的早上就被tarjan毁掉了（微笑
放资料qwq谢谢你们让我学会了tarjan
前两个还是让我了解了tarjan而最后一个可就厉害了还让我巩固了topo sort + DAG 上的dp！
学习笔记详见注释quq
1 #include2 #include 3 #include 4 #define maxn 10010 5 #define maxm 100010 6 using namespace std; 7 int n, m, num = 0, tim = 0, top = 0, cnt = 0; 8 int node[maxn], sd[maxn], head[maxm], dfn[maxn], low[maxn]; 9 //node 点权 sd 记录该点在哪个强连通分量中 head 原图的每一条边的起点 dfn时间戳 low能追溯到的最早的栈中节点编号 10 int sta[maxn], hear[maxm], dist[maxn], in[maxn];11 //sta 栈 为了存储整个强连通分量 hear 是新图中的每一条边的起点 dist 走到当前点（缩环成点结束后）的最大权值和 in每个点（依旧是缩点结束后）的入度 12 bool vis[maxn];// 记录当前该节点是否在栈中 13 struct edge {14 int nxt, to, from;15 }e[maxm], ed[maxm];16 int read() { //一个优美的快读 17 char ch = getchar(); int x = 0, f = 1;18 while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar();}19 while(ch <= '9' && ch >='0') {x = x * 10 + ch - '0'; ch = getchar();}20 return x * f;21 }22 void add(int from, int to) { //原图 23 e[++num].nxt = head[from];24 e[num].from = from;25 e[num].to = to;26 head[from] = num;27 }28 void readd(int from, int to) { //缩点之后重构图 29 in[to]++;//入度++ 30 ed[++cnt].nxt = hear[from];31 ed[cnt].from = from;32 ed[cnt].to = to;33 hear[from] = cnt;34 }35 void tarjan(int x) {36 low[x] = dfn[x] = ++tim;37 sta[++top] = x;38 vis[x] = 1;39 for(int i = head[x]; i; i = e[i].nxt) {40 int v = e[i].to;41 if(!dfn[v]) { //如果v未被访问 42 tarjan(v);43 low[x] = min(low[x], low[v]);44 }45 else if(vis[v]) low[x] = min(low[x], dfn[v]);//low[x] = min(low[x], low[v]) 两种写法等价 46 }47 if(dfn[x] == low[x]) { //是该强连通分量的根节点 48 int y;49 while(y = sta[top--]) {50 sd[y] = x;//y属于强连通分量x 51 vis[y] = 0;//退栈 52 if(x == y) break;//到自己了， 结束 53 node[x] += node[y];//把这个环上点的权值累加到根节点上 54 55 }56 }57 }58 int topo() { //拓扑排序 59 queue q;60 int tot = 0;61 for(int i = 1; i <= n; i++) {62 if(sd[i] == i && !in[i]) { //入度为0 且是所在的强连通的根节点 63 q.push(i);//入队 64 dist[i] = node[i];65 } 66 }67 while(!q.empty()) {68 int k = q.front();69 q.pop();70 for(int i = hear[k]; i; i = ed[i].nxt) {71 int v = ed[i].to;72 dist[v] = max(dist[v], dist[k] + node[v]); //dp过程 73 in[v]--;//入度-- 74 if(in[v] == 0) q.push(v);//更新队列 75 }76 }77 int ans = 0;78 for(int i = 1; i <= n; i++) 79 ans = max(ans, dist[i]);80 return ans;81 }82 int main() {83 scanf("%d%d", &n, &m);84 for(int i = 1; i <= n; i++) 85 node[i] = read();86 for(int i = 1; i <= m; i++) {87 int u = read(), v = read();88 add(u, v);89 }90 for(int i = 1; i <= n; i++) {91 if(!dfn[i]) tarjan(i);//孤立的点也是一个强连通分量， 为了保证每个点都遍历到， 所以tarjan一般在for中使用 92 }93 for(int i = 1; i <= m; i++) {94 int x = sd[e[i].from], y = sd[e[i].to];//如果两个点不在一个强连通分量中 95 if(x != y) readd(x, y);//缩点之后重构图 96 }97 printf("%d", topo());//转化为DAG上得dp 98 return 0;99 }