社区讨论

警示后人:如果你 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()
先介绍一个不用生成树改图为树和找成环的边的方法,就加了两行代码,改了下树剖的两个 dfs
CPP
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 后把环上的边权改成 00
然后没给 edges 开 22 倍的 maxmmaxm,gg。
为什么代码不会自己 debug 呢。

回复

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

正在加载回复...