一个小疑问
查看原帖
一个小疑问
416549
Kao_Potato楼主2023/11/24 21:14

如果这样写

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

其中 qltnqltn 为强联通分量的总数,就是从 11 开始拓扑序跑一遍

而如果这样写

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一个点

这份不也是从 11 开始按拓扑跑一遍吗,两份代码有什么不同

2023/11/24 21:14
加载中...