一、题目描述：
给你一个 $n$ 个点，$m$ 条边的有向图。点带权。
求一条路径经过的所有点的权值和最大是多少。点可以重复经过。
数据范围：$1 \le n \le 1 \times 10^4,1 \le m \le 1 \times 10^5$ 。
二、解题思路：
缩点板子题，不需要思路。时间复杂度 $O(n+m)$ 。
三、完整代码：
1 #include<iostream>
2 #include<vector>
3 #define N 10010
4 #define M 100010
5 using namespace std;
6 vector <int> s[N];
7 int n,m,l,r,cc,tot,maxx;
8 int f[N],q[N],d[N],in[N],val[N];
9 int dfn[N],ans[N],low[N],bel[N];
10 struct EDGE{
11 int v,nxt;
12 }edge[M];
13 int head[N],cnt;
14 void add(int u,int v)
15 {
16 edge[++cnt].v=v;
17 edge[cnt].nxt=head[u];
18 head[u]=cnt;
19 }
20 void tarjan(int u)
21 {
22 f[u]=1;q[++r]=u;dfn[u]=low[u]=++tot;
23 for(int i=head[u];i!=-1;i=edge[i].nxt)
24 {
25 int to=edge[i].v;if(!dfn[to])
26 tarjan(to),low[u]=min(low[u],low[to]);
27 else if(f[to]) low[u]=min(low[u],dfn[to]);
28 //我觉得更新low[u]原因只是为了
29 //让u知道他自己没资格做新的联通分量的起点
30 //有点比他更适合=>极大联通子图
31 }
32 if(dfn[u]==low[u])
33 {
34 cc++;do{
35 bel[q[r]]=cc,f[q[r]]=0;
36 s[cc].push_back(q[r]),r--;
37 }while(q[r+1]!=u);
38 //常规操作
39 }
40 }
41 int top_sort()
42 {
43 for(int i=1;i<=n;i++)
44 for(int j=head[i];j!=-1;j=edge[j].nxt)
45 if(bel[edge[j].v]!=bel[i])
46 in[bel[edge[j].v]]++;
47 l=1,r=0;
48 for(int i=1;i<=cc;i++)
49 if(!in[i])
50 q[++r]=i;
51 while(l<=r)
52 {
53 int u=q[l];l++;
54 for(int i:s[u])
55 ans[u]+=val[i];
56 for(int i:s[u])
57 for(int j=head[i];j!=-1;j=edge[j].nxt)
58 {
59 int to=bel[edge[j].v];
60 ans[to]=max(ans[to],ans[u]);
61 in[to]--;if(!in[to])q[++r]=to;
62 }
63 }
64 for(int i=1;i<=cc;i++)
65 maxx=max(maxx,ans[i]);
66 return maxx;
67 //感觉拓扑排序不是很必要，月赛写了个dfs也过了
68 }
69 int main()
70 {
71 ios::sync_with_stdio(false);
72 cin.tie(0);cout.tie(0);
73 cin>>n>>m;
74 for(int i=1;i<=n;i++)
75 cin>>val[i],head[i]=-1;
76 for(int i=1,u,v;i<=m;i++)
77 cin>>u>>v,add(u,v);
78 for(int i=1;i<=n;i++)
79 if(!dfn[i])
80 tarjan(i);
81 cout<<top_sort()<<'\n';
82 return 0;
83 }
四、写题心得：
好的，复习了缩点。众所周知初学是在昨天。收获经验如下：
$1、不要自己想奇怪的方法来写缩点，复杂度高还没正确性=> Exp++$
$2、vector\ 用起来很舒服，以后都不想用链式前向星了\ qwq=> Exp++$
标签：缩点,head,int,题解,P3387,++,dfn,low From： https://www.cnblogs.com/yhy-trh/p/17506664.html