level 10
说用法倒不如说是一种扩展的并查集..曾经做2010提高组第三题的时候想到的..翻了很多资料都没有提到的..如果有谁以前就知道就请直接无视吧.另欢迎X楼~
2011年02月21日 13点02分
2
level 10
题就不重复了..不知道的人可以去翻一下..
我们可以先定义树上两点间的距离为一点到另一点路径上线段的个数.显然两点间的距离与两点分别到跟的距离的差对于2是同余的..对于本题.我们对于在并查集上抽象出的树中使分别在两个监狱中的犯人间的距离为奇数.则在同一监狱内的犯人间的距离一定为偶数..通过该思路写出的东西跑起来效率与二分的做法差不多.当然如果你坚持认为是我测试器抽了我也没有方法..
2011年02月21日 14点02分
4
level 10
由于使用了并查集的模型必然想到需要路径压缩的.使用这个方法因为奇偶性的限制无法直接对路径进行直接压缩..需要先判定点到根的距离.为奇数则不在同一监狱可直接压缩.为偶数需要在中间随意接个中间变量进行压缩.但是经试验不进行路径压缩效率也非常不错.
2011年02月21日 14点02分
6
level 11
。。。。。。。。。。。。。LZ你不觉得只要在路径压缩的时候多维护一个信息就可以了么。。。。
2011年02月21日 14点02分
7
level 10
现在开始介绍整个算法..
首先对于读入的边进行排序以贪心求解.从大到小一次考虑每条边.如不在同一**中则直接判断一点到根的距离为偶数直接接入奇数从根接一个中间变量再接入.在同一**中由两点间距离进行判定.奇数忽略该边偶数则表示该边无法加入即为答案..算法的效率经本人完全不权威的测试效率还是不错的.并且比双并查集做法能够在一定程度上减小空间的使用量.
2011年02月21日 14点02分
9
level 10
写完了..坐等各位来喷..
ps:如果是原创的话申精..不是的话请直接无视我吧..
2011年02月21日 14点02分
11
level 8
我菜感觉楼主说的有点像双**icolored)树。说错了请无视。
2011年02月21日 14点02分
12
level 10
回复：12楼
表示比你要菜很多完全不懂你说的是什么= =
2011年02月21日 14点02分
13
level 10
回复：15楼
表示加了防和谐之后依旧不知道你在说什么..果然我太菜了啊= =
2011年02月21日 14点02分
16
level 5
我当时就是用的此法，当时想的是奇环偶环与二分图的关系，套用了克鲁斯卡尔算法，要比二分少一个log2(n)
2011年02月21日 14点02分
17
level 10
回复：17楼
克鲁斯卡尔=kruscal?请教您是怎么用上的..
2011年02月21日 14点02分
18
![[Kiss]](/static/emoticons/Kiss.png)