【郑重警示后人】关于此题常见错误对应的特判

WA #2

若 Boss 无论堵哪条边，其最短路均不变，那么

ans2=m

。

CPP

if(ans1==dis1[n]) ans2=m; //代表最短路完全没变

WA Subtask 1-1

若图上只存在一个点，那么

ans2=m

，即自环边数。

CPP

cout << ans1 << " " << (ans1==0?m:ans2) << endl;

WA Subtask 1-2

最短路链上

\forall e=(u,v)

，存在多条边权相等的边。

CPP

for(ri i=1;i<tim;i++) if(tree.querymin(1,1,tim,i,i).minval==ans1){
		int cnt=0,tmp=MAXN;
		for(ri j=0;j<orgedge[rnk[i]].size();j++){
			int u=rnk[i],v=orgedge[rnk[i]][j].first,w=orgedge[rnk[i]][j].second;
			if(dfn[u]+1==dfn[v]) tmp=min(tmp,w);
		}
		for(ri j=0;j<orgedge[rnk[i]].size();j++){
			int u=rnk[i],v=orgedge[rnk[i]][j].first,w=orgedge[rnk[i]][j].second;
			if(dfn[u]+1==dfn[v] && w==tmp) cnt++;
		}
		ans2+=cnt;
	}

【郑重警示后人】关于此题常见错误对应的特判

讨论操作

回复

相关推荐

【郑重警示后人】关于此题常见错误对应的特判