社区讨论
警示后人:如果你 RE 90 on test 7
P2542[AHOI2005] 航线规划参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lw7rwu5b
- 此快照首次捕获于
- 2024/05/15 20:03 2 年前
- 此快照最后确认于
- 2024/05/15 21:51 2 年前
可能没人会因为这个错误卡了 2h()
先介绍一个不用生成树改图为树和找成环的边的方法,就加了两行代码,改了下树剖的两个
CPPdfs :void dfs(int u){
son[u] = -1, siz[u] = 1;
int len = g[u].size();
for(int i = 0; i < len; i ++){
int v = g[u][i];
if(!dep[v]){
g0[u].push_back(v);//
dep[v] = dep[u] + 1;
fa[v] = u;
dfs(v);
siz[u] += siz[v];
if(son[u] == -1 || siz[v] > siz[son[u]]) son[u] = v;
}
else if(v != fa[u]) edges[++ edgecnt].first = u, edges[edgecnt].second = v;//
}
return ;
}
void dfs(int u, int t){
top[u] = t, dfn[u] = ++ cnt, rnk[cnt] = u;
if(son[u] == -1) return ;
dfs(son[u], t);
int len = g0[u].size();
for(int i = 0; i < len; i ++){
int v = g0[u][i];
if(v != son[u] && v != fa[u]) dfs(v, v);
}
return ;
}
然后连了双向边,开了存新树的邻接表 g0,还有存成环的边的
pair 数组 edges,在树剖的第一个 dfs 里找成环的边,如果找到之前跑过并且不是父亲的点就存起来,跑完树剖的两个 dfs 后把环上的边权改成 。然后没给 edges 开 倍的 ,gg。
为什么代码不会自己 debug 呢。
回复
共 0 条回复,欢迎继续交流。
正在加载回复...