社区讨论

京师后人

P5236【模板】静态仙人掌参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mkpi6tr4
此快照首次捕获于
2026/01/22 21:44
4 周前
此快照最后确认于
2026/01/23 17:08
4 周前
查看原帖
如果你使用广义圆方树并且是使用了一个数组存储返祖边(假定是val数组)的边权,那么请注意你的tarjan:
  • 不要让父节点进入
CPP
else if(dfn[v]<dfn[u]){
/*这里不能直接else而是要判断dfn[v]<dfn[u],因为如果不判可能会走到环和当前节点连接的另一个点,导致val存的值错误,不过我写的时候注意到了,这里提一嘴*/
  low[u]=min(low[u],dfn[v]);
  val[u]=c[i];
}
(就是low数组进行取min,并且用边权数组c更新val数组),直接在前面把fa判掉
  • 在进入下一层Tarjan之前,将val数组先 置为这条边的边权
CPP
if(!dfn[v]){
  dpc[v]=dpc[u]+c[i];
  val[v]=c[i];//这个
  tarjan(v,i);
...
}
这样做是为了在下一层只有一个点,形成2点1线时,让代码计算环长为这条边长的两倍,从而正确计算圆方树上的边权,不然代码会认为边上还有一个代价为0的路径走上去

回复

1 条回复,欢迎继续交流。

正在加载回复...