UOJ Logo AntiLeaf的博客

博客

#79 一般图最大匹配 求hack

2017-05-26 16:34:40 By AntiLeaf

前两天学了学高斯消元版的一般图最大匹配,抄了抄各位dalao们的代码

今天重新看自己写的代码,发现有一个地方抄错了

//In function Gauss(int A[][maxn],int B[][maxn],n)
if(B){
    swap(id[i],id[j]);
    for(int k=1;k<=n;k++)swap(B[i][k],B[j][k]);
}

而代码里对Gauss这个函数的两次调用分别是这样的

Gauss(A,NULL,n);
......
Gauss(A,B,n);

第一次高斯消元是为了找出所有在最大匹配中的点,但由于高斯消元的过程中可能会进行行的交换,因此需要维护一个id数组表示每个点对应的行号

(讲真其实还是没明白为啥这个东西是每个点对应的行号,不应该是每行对应的点的编号么……然而这样又解释不清代码在写什么了,囧囧囧……)

然而正常的写法应该是在第一次高斯消元时维护id[],第二次高斯消元时维护与否都无所谓了,显然我这个是搞反了

但是还是可以过掉所有的数据和hack数据,手动构造了几组也卡不掉,感觉很神奇

这个代码应该是错的了,数据的构造思路应该是找一个点$x$($x>1$)使得$x$和$1$之间有连边但$x$不可能在最大匹配中,但是想了想并没有找到满足这种情况的数据

因此写了这篇博客,虚心请求诸位dalao提供一组hack数据,以解心中疑问,如有dalao愿意相助,不胜感激……

评论

qmqmqm
找一个点x(x>1)使得x和1之间有连边但x不可能在最大匹配中是不可能的,因为你考虑一个匹配,如果1和x均不是匹配点,那么加入1和x之后更优,如果1是匹配点,那么去掉1对应的匹配边,加入1和x,答案不变。所以x一定可以在最大匹配中。

发表评论

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