社区讨论
警示后人,会wa第十个点的原因
P5058[ZJOI2004] 嗅探器参与者 9已保存回复 8
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 8 条
- 当前快照
- 1 份
- 快照标识符
- @lo8kd79l
- 此快照首次捕获于
- 2023/10/27 20:02 2 年前
- 此快照最后确认于
- 2023/10/27 20:02 2 年前
应该wa了第十个点的人看了题解或讨论都知道,判断条件要写
dfn[v]<=dfn[b]而不是dfn[u]<dfn[b],那这是为什么呢?我们可以来看一下这一组数据:
CPP7
5 1
1 2
2 6
2 3
3 4
4 5
6 7
0 0
1 3
建出来的图是这样的:


然而我们会发现,写前者跑出来的正解是 No solution,而后者却跑出来了 。这是因为在从 搜 这课子树时, 已经处理出来是 ,而 是 ,会错误地判断出“ 阻断了 和 之间的道路”这一结论,而严格地搜索子树 则不会出错。
见到很多题解没有解释该写法错误的原因,故发此帖,顺便提供一组小 hack 数据。
ps:若用邻接表,可以将数据中的
5 1和2 6放到后面,主要是为了先搜到 再搜到 。回复
共 8 条回复,欢迎继续交流。
正在加载回复...