萌新已疯,求助匈牙利算法
查看原帖
萌新已疯,求助匈牙利算法
164432
suxxsfekkksd11楼主2020/5/22 02:29

按照第一个题解的思路,就是找每个点如果和他的 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;
}
2020/5/22 02:29
加载中...