UOJ Logo bzoj的博客

博客

一般图最大匹配的随机匹配hack法

2017-03-30 22:36:02 By bzoj

题目#79有一种怪异的做法,就是随机多次改变边的顺序然后和二分图一样增广,如果多次都没找到增广路才退出。

这种做法思维难度和代码难度都比带花树算法小,所以有不少提交采用了这个做法

然而它是可以被卡掉的。。

首先,要卡掉它的图必须有许多奇环。。因为它在没有奇环的图上跑起来是和二分图一样的,而这个做法在二分图上是对的。

然而你就算生成一个全是三角形连在一起的图,如果他常数卡的好,随机次数多,还是有很大概率卡不掉的。。

所以,这时候就要用到一个神奇的做法——加入无用边

具体来说,加入大量不可能出现在任何一个原图的最大匹配中的边,使得它的随机增广很容易随机到这些边从而瞬间爆炸!炸弹熊

然而这产生了一个问题,就是如何保证大量的边都不会出现在最大匹配中?思考熊

做法很简单——在所有奇数节点间连成一个团,而每个偶数节点只和其对应的一或两个奇数节点连边,这样的图既有大量的奇环,也有大量的无用边,通过这种方式生成的图在custom test上测试十次,全部没有随机得到最大匹配。鼓掌熊

如果你要出的一般图最大匹配的题目的图是由输入通过某种操作得到的,也可以考虑如何构造输入使得得到的图的奇环和无用边尽可能多,来卡掉这种算法。

评论

WAAutoMaton
对于[这个](http://uoj.ac/submission/237587)提交,您的做法好像叉不掉呀

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。