按照第一个题解的思路,就是找每个点如果和他的 match 强制不让他们匹配,那么还有没有增广路
我用的 bfs,就是把当前这个点和他的match的match都设为0(就是达到不让匹配的目的),然后把他的match加入队列跑一遍bfs
最后再把刚才清零的match还原
其它函数和题解的中间变量输出是一样的,所以应该是没错,所以错误肯定在bfs函数里
球大佬查错
inline int bfs(int xi,int xj){
reg int u,v;
u=get_id(xi,xj);
if(!match[u]) return 0;
int tmp=match[u];
tail=0;head=-1;que[++head]=tmp;
std::memset(check,0,sizeof check);check[tmp]=check[u]=1;
match[tmp]=match[u]=0;
int uu=u;
while(tail<=head){
u=que[tail++];
for(reg int i=G.fir[u];i;i=G.nex[i]){
v=G.to[i];
if(check[v]) continue;
check[v]=1;
if(match[v]) que[++head]=match[v];
else goto RETURN;//有增广路
}
}
match[tmp]=uu;match[uu]=tmp;
return 1;
RETURN:;
match[tmp]=uu;match[uu]=tmp;
return 0;
}