前两天学了学高斯消元版的一般图最大匹配,抄了抄各位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愿意相助,不胜感激……