UOJ Logo AntiLeaf的博客

博客

共找到 1 篇包含 “一般图匹配” 标签的博客:

#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愿意相助,不胜感激……