改了下,现在全WA了QWQ
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <stack>
using namespace std;
typedef long long ll;
const ll MAXN=1e5+5;
struct edge{
ll from,to,nxt;
}e[MAXN],e1[MAXN];
ll head[MAXN],tot;
void add(ll u,ll v,edge E[]){
E[++tot].nxt=head[u];
head[u]=tot;
E[tot].from=u;
E[tot].to=v;
}
ll pre[MAXN],low[MAXN],dt,sccNo[MAXN],sccCount,value[MAXN],a[MAXN];
stack<ll>s;
ll ins[MAXN];
void tarjan(ll u){
++dt;
pre[u]=low[u]=dt;
s.push(u);
ins[u]= true;
for (ll i = head[u]; i ; i=e[head[i]].nxt) {
ll v=e[i].to;
if(!pre[v]){
tarjan(v);
low[u]= min(low[u],low[v]);
}else if(sccNo[v]==0){
//cout<<u<<" "<<v<<" "<<low[u]<<" "<<pre[v]<<" "<<sccNo[u]<<" "<<e[head[u]].nxt<<" "<<e[e[head[u]].nxt].to<<" "<<endl;
low[u]= min(low[u],pre[v]);
}
}
if(pre[u]==low[u]){
sccCount++;
while (true){
ll t=s.top();
s.pop();
ins[t]= false;
sccNo[t]=sccCount;
value[sccCount]+=a[t];
if(t==u){
break;
}
}
}
return;
}
ll f[MAXN];
void dfs(ll u){
if(f[u]){
return;
}
f[u]=value[u];
ll Max=0;
for (int i = head[u]; i ; i=e1[head[i]].nxt) {
dfs(e1[i].to);
Max= max(Max,f[e[i].to]);
}
f[u]+=Max;
}
ll n,m;
int main(){
scanf("%lld%lld",&n,&m);
for (int i = 1; i <=n ; ++i) {
scanf("%lld",&a[i]);
}
for (int i = 1; i <=m ; ++i) {
ll u,v;
scanf("%lld%lld",&u,&v);
add(u,v,e);
//cout<<tot<<" "<<e[tot].from<<" "<<e[tot].to<<" "<<e[tot].nxt<<endl;
}
for (int i = 1; i <=n ; ++i) {
if(pre[i]==0){
tarjan(i);
}
}
memset(head,0,sizeof(head));
tot=0;
for (int i = 1; i <=m ; ++i) {
if(sccNo[e[i].to]!=sccNo[e[i].from]){
add(sccNo[e[i].from],sccNo[e[i].to],e1);
}
}
ll ans=0;
for (int i = 1; i <=sccCount ; ++i) {
if(!f[i]){
dfs(i);
ans= max(ans,f[i]);
}
}
printf("%lld\n",ans);
return 0;
}
```
by tanghg @ 2023-01-06 10:11:55
@[tanghg](/user/692647) ```for```循环里的应该 ```i=e[head[u]].nxt```是啥逆天操作,不应该是```i=e[i].nxt```?
by MarchKid_J0e @ 2023-01-06 10:14:27
@[tanghg](/user/692647) 不会对链式前向星有啥误解吧。[流汗黄豆]
by MarchKid_J0e @ 2023-01-06 10:16:15
@[tanghg](/user/692647) 然后把 dfs 稍微修改一下,直接以每个点为起点搜索,搜索过程中取最大值就行了,不用考虑啥遍历没遍历过,**缩完点后的图无环**。
这个题没了,改后的代码:
```cpp
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <stack>
using namespace std;
typedef long long ll;
const ll MAXN=1e5+5;
struct edge{
ll from,to,nxt;
}e[MAXN],e1[MAXN];
ll head[MAXN],tot;
void add(ll u,ll v,edge E[]){
E[++tot].nxt=head[u];
head[u]=tot;
E[tot].from=u;
E[tot].to=v;
}
ll pre[MAXN],low[MAXN],dt,sccNo[MAXN],sccCount,value[MAXN],a[MAXN];
stack<ll>s;
ll ins[MAXN];
void tarjan(ll u){
++dt;
pre[u]=low[u]=dt;
s.push(u);
ins[u]= true;
for (ll i = head[u]; i ; i=e[i].nxt) {
ll v=e[i].to;
if(!pre[v]){
tarjan(v);
low[u]= min(low[u],low[v]);
}else if(sccNo[v]==0){
//cout<<u<<" "<<v<<" "<<low[u]<<" "<<pre[v]<<" "<<sccNo[u]<<" "<<e[head[u]].nxt<<" "<<e[e[head[u]].nxt].to<<" "<<endl;
low[u]= min(low[u],pre[v]);
}
}
if(pre[u]==low[u]){
sccCount++;
while (true){
ll t=s.top();
s.pop();
ins[t]= false;
sccNo[t]=sccCount;
value[sccCount]+=a[t];
if(t==u){
break;
}
}
}
return;
}
//ll f[MAXN];
ll ans = 0;
void dfs(ll u, ll Max){
// if(f[u]){
// return;
// }
// f[u]=value[u];
// ll Max=0;
ans = max(ans, Max);
for (int i = head[u]; i ; i=e1[i].nxt) {
dfs(e1[i].to, Max + value[e1[i].to]);
// Max= max(Max,f[e[i].to]);
}
// f[u]+=Max;
}
ll n,m;
int main(){
scanf("%lld%lld",&n,&m);
for (int i = 1; i <=n ; ++i) {
scanf("%lld",&a[i]);
}
for (int i = 1; i <=m ; ++i) {
ll u,v;
scanf("%lld%lld",&u,&v);
add(u,v,e);
//cout<<tot<<" "<<e[tot].from<<" "<<e[tot].to<<" "<<e[tot].nxt<<endl;
}
for (int i = 1; i <=n ; ++i) {
if(pre[i]==0){
tarjan(i);
}
}
memset(head,0,sizeof(head));
tot=0;
for (int i = 1; i <=m ; ++i) {
if(sccNo[e[i].to]!=sccNo[e[i].from]){
add(sccNo[e[i].from],sccNo[e[i].to],e1);
}
}
for (int i = 1; i <=sccCount ; ++i) {
// if(!f[i]){
dfs(i,value[i]);
// ans= max(ans,f[i]);
// }
}
printf("%lld\n",ans);
return 0;
}
```
by MarchKid_Joe @ 2023-01-06 10:25:39
所以错误就是:
链式前向星的遍历
dfs 的过程
by MarchKid_Joe @ 2023-01-06 10:26:28
@[MarchKid_Joe](/user/239163) 看出来了,还在调,谢谢您了
by tanghg @ 2023-01-06 10:32:34
谢谢大佬们,链式前向星没咋用过,手滑。。。
by tanghg @ 2023-01-06 10:33:32
过啦,谢谢大家
by tanghg @ 2023-01-06 10:38:20
@[MarchKid_J0e](/user/760799) 昨天睡的有点晚今天脑抽了,我是咋写出来的`e[head[u]].nxt`的。谢谢您
by tanghg @ 2023-01-06 10:39:40