求DAG中一条最大点权链用scc缩点完成后其实问题就回到了DAG，这样一个问题，开始dfs写多了，直接找入度为0为起点一个dfs，结果就搜爆了。正解：寻找DAG中一个拓扑排序，按照拓扑序遍历点，再遍历点的边，dp维护答案而Tarjan缩点完成后新点的倒序（ans_scc->1）就是一个拓扑序,于

在洛谷中查看所有思考都在代码，可以结合代码思考谢谢~#include<bits/stdc++.h>usingnamespacestd;constintN=1e4+5;intn,m,val[N];intdfn[N],low[N],num,col[N],cnt;//col记录每个点属于哪个联通分量//num记录遍历时间cnt记录缩点完后有多少个点in

一、题目描述：给你一个$n$个点，$m$条边的有向图。点带权。求一条路径经过的所有点的权值和最大是多少。点可以重复经过。数据范围：$1\len\le1\times10^4,1\lem\le1\times10^5$。 二、解题思路：缩点板子题，不需要思路。时间复杂度$O(n+m)$。

 缩点求DAG最长路#include<bits/stdc++.h>usingnamespacestd;constintN=1e4+2;intn,m,pool,a[N];intlow[N],dfn[N];intkcnt,id[N];intf[N],v

#include<iostream>#include<queue>#include<vector>usingnamespacestd;constintN=1e4+1;intn,m;vector<int>to[N];intval[N];voidadd

P3387我的做法就是将原图缩点，得到一个DAG新图，在新图上进行DP求最长路径。1#include<bits/stdc++.h>2usingnamespacestd;3constintN=1e5+10;4intn,