hack

P2731 [USACO3.3] 骑马修栅栏 Riding the Fences

Godのfather @ 2020-10-10 21:26:07

数据:

input

3
2 3
3 4
4 2

output

2
3
4
2

然而,经过测试,包括第一篇题解在内的很多题解输出结果是错误的(会输出"1")。

原因:(简称度数为奇数的点为奇点,度数为偶数的点为偶点)

题目中并没有保证给出的图是半欧拉图。所以,起始点要分类讨论(半欧拉图的起点是奇点,欧拉图的起点是偶点)。

但是,测试数据中,有且仅有一个点是欧拉图,并且该欧拉图中欧拉回路的起点恰好为1,这就使得没有分类讨论的程序也AC了此题。

因为本题的意图还是求欧拉路,所以就不请求增强数据或者撤下题解了


by QianianXY @ 2020-10-10 21:40:53

@Godのfather %%%

膜dalao明天即可rp++(


by 渔歌 @ 2021-02-21 19:20:33

@Godのfather dalao题目中说了各个栅栏编号是从1开始的···可能你没注意到


by 渔歌 @ 2021-02-21 20:33:07

@ZYCsdnx 不过数据里面确实不连续···这就是一个问题了


by _Luminescence_ @ 2022-08-19 10:21:01

感谢!


|