这种代码真心觉得别调了，重写更快，真心的
by EDqwq @ 2020-09-14 14:16:34
@[林深时x见鹿](/user/294562) 代码一定要调试，这才能充分明白什么叫小错误，也可以加深理解。（狗头）。
by JK_LOVER @ 2020-09-14 15:09:50
@[SfumatoCannon_](/user/125429) |||
```cpp
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
int n,m1,m2,timea;
int p[101001],h1[100101],h2[101001],f[100011],dfn[110001],low[101001];
stack<int> st;
int vis[100101],dp[101001],rd[101001];
struct Edge
{
int from,next,to;
};
Edge bian1[1000011],bian2[1010001];
void add1(int x,int y,int id)
{
bian1[id].from=x;
bian1[id].to=y;
bian1[id].next=h1[x];
h1[x]=id;
}
void add2(int x,int y)
{
m2++;
bian2[m2].from=x;
bian2[m2].to=y;
bian2[m2].next=h2[x];
h2[x]=m2;
rd[y]++;
}
int xzc[11010101];
void tarjan(int x)
{
timea++;
dfn[x]=low[x]=timea;
st.push(x);xzc[x] = 1;
int i,j;
for (i=h1[x];i;i=bian1[i].next)
{
j=bian1[i].to;
if (dfn[j]==0)
{
tarjan(j);
low[x]=min(low[x],low[j]);
}
else
if(xzc[j])low[x]=min(low[x],dfn[j]);
}
if (dfn[x]==low[x])
{
while (st.top()!=x)
{
p[x]+=p[st.top()];
f[st.top()]=x;xzc[st.top()] = 0;
st.pop();
}
f[x]=x;xzc[x] = 0;
st.pop();
}
}
void lb()
{
int i;
for (i=1;i<=m1;i++)
{
if (f[bian1[i].from]!=f[bian1[i].to])
add2(f[bian1[i].from],f[bian1[i].to]);
}
}
int topo()
{
queue<int> Q;
int i;
for (i=1;i<=n;i++)
if (f[i]==i&&rd[i]==0)
{
Q.push(i);
dp[i]=p[i];
}
while (!Q.empty())
{
int k=Q.front();
Q.pop();
for (i=h2[k];i;i=bian2[i].next)
{
dp[bian2[i].to]=max(dp[bian2[i].to],dp[k]+p[bian2[i].to]);
rd[bian2[i].to]--;
if (rd[bian2[i].to]==0)
Q.push(bian2[i].to);
}
}
int ans=0;
for (i=1;i<=n;i++)
ans=max(ans,dp[i]);
return ans;
}
int main()
{
cin>>n>>m1;
int i,x,y;
for (i=1;i<=n;i++)
cin>>p[i];
for (i=1;i<=m1;i++)
{
cin>>x>>y;
add1(x,y,i);
}
for (i=1;i<=n;i++)
f[i]=i;
for (i=1;i<=n;i++)
if (!dfn[i])
tarjan(i);
lb();
cout<<topo();
return 0;
}
```
by JK_LOVER @ 2020-09-14 15:17:06
@[SfumatoCannon_](/user/125429) 要记住tarjan算法时，要考虑 **to** 是否还在 **栈** 中，这是tarjan算法正确性的保证。
```cpp
int xzc[11010101];
void tarjan(int x)
{
timea++;
dfn[x]=low[x]=timea;
st.push(x);xzc[x] = 1;
int i,j;
for (i=h1[x];i;i=bian1[i].next)
{
j=bian1[i].to;
if (dfn[j]==0)
{
tarjan(j);
low[x]=min(low[x],low[j]);
}
else
if(xzc[j])low[x]=min(low[x],dfn[j]);
}
```
by JK_LOVER @ 2020-09-14 15:18:44
@[JK_LOVER](/user/227824) Orz，果然我还是菜了，谢谢大佬
by SfumatoCannon_ @ 2020-09-14 19:38:46
此帖完结
by SfumatoCannon_ @ 2020-09-14 19:39:19