@[33616354czf411](/space/show?uid=21082) 您拓扑排序遍历图的时候 用成旧图了
by Burnside @ 2018-11-08 20:53:43
@[Burnside](/space/show?uid=64500) emmmmm我觉得我没救了--
by Herry_NY @ 2018-11-08 21:00:16
@[Burnside](/space/show?uid=64500) O(∩_∩)O谢谢
by Herry_NY @ 2018-11-08 21:00:37
@Burnside改成这样了可还是挂了--
```
void topu(){
queue<int>q;
For(i,1,n)if(be[i]==i&&!in[i])q.push(i),dis[i]=w[i];
while(!q.empty()){
int u=q.front();q.pop();
for(ri i=head1[u];i;i=e1[i].next){
int v=e1[i].v;
dis[v]=max(dis[v],dis[u]+w[v]);
in[v]--;
if(!in[v])q.push(v);
}
}
int ans=0;
For(i,1,n)ans=max(ans,dis[i]);
printf("%d\n",ans);
}
```
by Herry_NY @ 2018-11-08 21:01:43
@[Burnside](/space/show?uid=64500)
by Herry_NY @ 2018-11-08 21:06:42
```cpp
For(i,1,m){
int u=e[i].u,v=e[i].v;
if(be[u]!=be[v])add1(u,v);in[v]++;
}
```
这个地方，应该是这样吧
```cpp
For(i,1,m){
int u=e[i].u,v=e[i].v;
if(be[u]!=be[v])add1(u,v),in[v]++;
}
```
by Burnside @ 2018-11-08 21:07:07
@[Burnside](/space/show?uid=64500) 谢谢谢谢解决了
by Herry_NY @ 2018-11-08 21:31:51
@[Burnside](/space/show?uid=64500) 40分什么鬼啊QAQ
by Herry_NY @ 2018-11-08 21:32:37
```
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ri register int
#define For(i,j,k) for(ri i=j;i<=k;i=-~i)
#define Dfor(i,j,k) for(ri i=j;i>=k;i=~-i)
#define gc() getchar()
template <class T>inline void read(T&x){
bool f;char ch=gc();
for(f=0;!isdigit(ch);ch=gc())if(ch=='-')f=1;
for(x=0;isdigit(ch);x=x*10+ch-'0',ch=gc());
x*=f==1?-1:1;
}
const int maxn=1e4+5;
bool bok[maxn];
int low[maxn],dfn[maxn],be[maxn],n,m,head[maxn],w[maxn],stac[maxn],top,cnt,head1[maxn],now,tim,in[maxn],dis[maxn];
struct node{
int u,v,next;
}e[maxn*10];
struct note{
int u,v,next;
}e1[maxn*10];
inline void add(int u,int v){
e[++now].u=u;
e[now].v=v;
e[now].next=head[u];
head[u]=now;
}
inline void add1(int u,int v){
e1[++now].u=u;
e1[now].v=v;
e1[now].next=head1[u];
head1[u]=now;
}
void tarjan(int u){
dfn[u]=low[u]=++tim;
bok[u]=1;
stac[++top]=u;
for(ri i=head[u];i;i=e[i].next){
int v=e[i].v;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}else if(bok[v])low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
cnt++;
int j;
while(1){
j=stac[top--];
be[j]=cnt;
bok[j]=0;
if(j==u)break;
w[u]+=w[j];
}
}
}
void topu(){
queue<int>q;
For(i,1,n)if(be[i]==i&&!in[i])q.push(i),dis[i]=w[i];
while(!q.empty()){
int u=q.front();q.pop();
for(ri i=head1[u];i;i=e1[i].next){
int v=e1[i].v;
dis[v]=max(dis[v],dis[u]+w[v]);
in[v]--;
if(!in[v])q.push(v);
}
}
int ans=0;
For(i,1,n)ans=max(ans,dis[i]);
printf("%d\n",ans);
}
int main(){
read(n),read(m);
For(i,1,n)read(w[i]);
for(ri i=1,u,v;i<=m;i=-~i)read(u),read(v),add(u,v);now=0;
For(i,1,n)if(!dfn[i])tarjan(i);
For(i,1,m){
int u=e[i].u,v=e[i].v;
if(be[u]!=be[v])add1(u,v),in[v]++;
}
topu();
return 0;
}
```
by Herry_NY @ 2018-11-08 21:32:58
@[33616354czf411](/space/show?uid=21082)
其实我没大看懂这个缩点的过程，那个$cnt$是个啥，我一般的习惯性写法是这样。
```cpp
if(dfn[u]==low[u]){
int j;
while(1){
j=stac[top--];
be[j]=u;
bok[j]=0;
if(j==u)break;
w[u]+=w[j];
}
}
```
by Burnside @ 2018-11-08 22:04:11