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 10
现在开始介绍整个算法..
首先对于读入的边进行排序以贪心求解.从大到小一次考虑每条边.如不在同一**中则直接判断一点到根的距离为偶数直接接入奇数从根接一个中间变量再接入.在同一**中由两点间距离进行判定.奇数忽略该边偶数则表示该边无法加入即为答案..算法的效率经本人完全不权威的测试效率还是不错的.并且比双并查集做法能够在一定程度上减小空间的使用量.
2011年02月21日 14点02分
9
level 10
写完了..坐等各位来喷..
ps:如果是原创的话申精..不是的话请直接无视我吧..
2011年02月21日 14点02分
11
level 10
回复：12楼
表示比你要菜很多完全不懂你说的是什么= =
2011年02月21日 14点02分
13
level 10
回复：15楼
表示加了防和谐之后依旧不知道你在说什么..果然我太菜了啊= =
2011年02月21日 14点02分
16
level 10
回复：17楼
克鲁斯卡尔=kruscal?请教您是怎么用上的..
2011年02月21日 14点02分
18
level 10
回复：21楼
但是找环会很麻烦啊..而且无法进行压缩的
2011年02月21日 14点02分
22
level 10
回复：27楼
多谢指教= = 神牛的空间气场太强不敢去啊..
2011年02月21日 15点02分
28
level 10
回复：29楼
考试的时候学了不到一个月连冰茶几是什么都不知道的表示比你们都菜太多了..
2011年02月21日 15点02分
31
level 10
回复：32楼
尽管说了很多次但我还是要说的..装菜掉RP啊
2011年02月21日 16点02分
33
![[Kiss]](/static/emoticons/Kiss.png)