如果这样写
int x=0;
for(int j=qltn;j>0;j--){
if(qlt[1]==j){
x=1;
}
if(x==0){
continue;
}
for(int i=first2[j];i!=0;i=b2[i].next){
p2n[b2[i].to]=min(p2n[b2[i].to],p2n[j]);
dp[b2[i].to]=max(max(dp[j],dp[b2[i].to]),max(p2x[j]-p2n[j],p2x[b2[i].to]-p2n[b2[i].to]));
}
}
就能够AC
其中 qltn 为强联通分量的总数,就是从 1 开始拓扑序跑一遍
而如果这样写
q.push(qlt[1]);
while(q.empty()==0){
int now=q.front();
q.pop();
for(int i=first2[now];i!=0;i=b2[i].next){
p2n[b2[i].to]=min(p2n[b2[i].to],p2n[now]);
dp[b2[i].to]=max(max(dp[now],dp[b2[i].to]),max(p2x[now]-p2n[now],p2x[b2[i].to]-p2n[b2[i].to]));
if(bj[b2[i].to]==0){
q.push(b2[i].to);
bj[b2[i].to]=1;
}
}
}
就会WA一个点
这份不也是从 1 开始按拓扑跑一遍吗,两份代码有什么不同