~~这里还有份压缩版~~
```cpp
//Tarjan 模板
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXX 10005
int n,m,x[MAXX*10],y[MAXX*10];
vector<int> t[MAXX],f[MAXX];//原图 缩点后图
stack<int> stk;//栈
int val[MAXX],sum[MAXX],dfsn[MAXX],low[MAXX],scc[MAXX],instk[MAXX],cnt;
// 点权 连通块权值和 dfs编号 最早到的点 所在强连通块编号 是否在块内 总数
int su[MAXX],ma[MAXX],ans;//记录入度 单点值 答案
void Tarjan(int pos,int tp){//点 编号
dfsn[pos]=low[pos]=tp;
stk.push(pos),instk[pos]=1;
for(auto it:t[pos]){
if(dfsn[it]==0)
Tarjan(it,tp+1),low[pos]=min(low[pos],low[it]);
else if(instk[it]) low[pos]=min(low[pos],dfsn[it]);//注意!!!
}
if(dfsn[pos]==low[pos]){
cnt++; int top;
do{
top=stk.top(),stk.pop();
instk[top]=0,sum[cnt]+=val[top],scc[top]=cnt;
}while(top!=pos);
}
}
inline ll read();
int main (){
n=read(),m=read();
for(int i=1;i<=n;++i) val[i]=read();
for(int i=1;i<=m;++i)
x[i]=read(),y[i]=read(),t[x[i]].push_back(y[i]);
//缩点:Tarjan
for(int i=1;i<=n;++i) if(!dfsn[i]) Tarjan(i,1);
for(int i=1;i<=m;++i) if(scc[x[i]]!=scc[y[i]]) f[scc[x[i]]].push_back(scc[y[i]]),su[scc[y[i]]]++;
//权值计算:拓扑排序
queue<int> q;//入度为0的点
for(int i=1;i<=cnt;i++) if(su[i]==0) q.push(i);
while(!q.empty()){
int qwe=q.front(); q.pop();
for(auto it:f[qwe]){
su[it]--,ma[it]=max(ma[it],ma[qwe]+sum[qwe]);
if(su[it]==0) q.push(it);
}
}
for(int i=1;i<=cnt;i++) ans=max(ans,ma[i]+sum[i]);
cout<<ans<<endl;
return 0;
}
inline ll read(){
ll k=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar();}
while(ch>='0' && ch<='9') k=k*10+ch-'0',ch=getchar();
return k*f;
}
```
by orgn @ 2023-01-12 23:26:47
找到了,望诸位引以为戒
`Tarjan`的`tp(或者说是dfs编号)`不可以存在函数变量中(悲),因为不可能都是链
(~~话说数据怎么这么多链~~
附上AC代码
```cpp
//Tarjan 模板
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXX 10005
int n,m,x[MAXX*10],y[MAXX*10];
vector<int> t[MAXX],f[MAXX];//原图 缩点后图
stack<int> stk;//栈
int val[MAXX],sum[MAXX],dfsn[MAXX],low[MAXX],scc[MAXX],instk[MAXX],cnt,tp;
// 点权 连通块权值和 dfs编号 最早到的点 所在强连通块编号 是否在块内 总数 dfs序编号
int su[MAXX],ma[MAXX],ans;//记录入度 单点值 答案
void Tarjan(int pos){//点 编号
dfsn[pos]=low[pos]=++tp;
stk.push(pos),instk[pos]=1;
for(auto it:t[pos]){
if(!dfsn[it])
Tarjan(it),low[pos]=min(low[pos],low[it]);
else if(instk[it]) low[pos]=min(low[pos],dfsn[it]);//注意!!!
}
if(dfsn[pos]==low[pos]){
cnt++; int top;
do{
top=stk.top(),stk.pop();
instk[top]=0,sum[cnt]+=val[top],scc[top]=cnt;
}while(top!=pos);
}
}
inline ll read();
int main (){
n=read(),m=read();
for(int i=1;i<=n;++i) val[i]=read();
for(int i=1;i<=m;++i)
x[i]=read(),y[i]=read(),t[x[i]].push_back(y[i]);
//缩点:Tarjan
for(int i=1;i<=n;++i) if(!dfsn[i]) Tarjan(i);
for(int i=1;i<=m;++i) if(scc[x[i]]!=scc[y[i]]) f[scc[x[i]]].push_back(scc[y[i]]),su[scc[y[i]]]++;
//权值计算:拓扑排序
queue<int> q;//入度为0的点
for(int i=1;i<=cnt;i++) if(su[i]==0) q.push(i);
while(!q.empty()){
int qwe=q.front(); q.pop();
for(auto it:f[qwe]){
su[it]--,ma[it]=max(ma[it],ma[qwe]+sum[qwe]);
if(!su[it]) q.push(it);
}
}
for(int i=1;i<=cnt;i++) ans=max(ans,ma[i]+sum[i]);
cout<<ans<<endl;
return 0;
}
inline ll read(){
ll k=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar();}
while(ch>='0' && ch<='9') k=k*10+ch-'0',ch=getchar();
return k*f;
}
```
by orgn @ 2023-01-12 23:34:12