UVa 1670 – NEERC2011K – Kingdom Roadmap

图论构造,需要我们在给出的树上补一些边,使得得到的新图删除任意一条边都是联通的。

错误思路:找到左右度为1的点然后两两连起来。反例如下图,红色的边是按照这个规则连出来的边,但是如果切断边$(u,v)$,则图不联通。


正确做法是按照DFS序找出度数为1的点,假设一共x个点,那么按照$(1, \lfloor \frac{n}{2} \rfloor)$,$(2, \lfloor \frac{n}{2}  \rfloor + 1)$,$(3, \lfloor \frac{n}{2}  \rfloor + 2)$ …… $(i, \lfloor \frac{n}{2} \rfloor + i – 1)$。

具体我也不知道为啥,我在做的时候是DFS之后把$(i, i +2)$匹配,这样就会有重复了。

 

说点什么

avatar
50
  Subscribe  
提醒