匈牙利算法可以加当前弧优化吗
查看原帖
匈牙利算法可以加当前弧优化吗
483966
一粒夸克楼主2021/6/30 20:04

这样写会 WAWA 一个点

bool dfs(int x,int tmp){
	if(vis[x]==tmp)return 0;
	vis[x]=tmp;
	for(int i=head[x];i;i=ne[i]){
		int u=ver[i];head[x]=i;
		if(!owr[u]||dfs(owr[u],tmp)){
			owr[u]=x;
			return 1;
		}
	}
	return 0;
}

下面两种写法都是能过的

bool dfs(int x,int tmp){
	if(vis[x]==tmp)return 0;
	vis[x]=tmp;
	for(int i=head[x];i;i=ne[i]){
		int u=ver[i];
		if(!owr[u]||dfs(owr[u],tmp)){
			owr[u]=x;
			return 1;
		}head[x]=i;
	}
	return 0;
}
bool dfs(int x,int tmp){
	if(vis[x]==tmp)return 0;
	vis[x]=tmp;
	for(int i=head[x];i;i=ne[i]){
		int u=ver[i];
		if(!owr[u]||dfs(owr[u],tmp)){
			owr[u]=x;
			return 1;
		}
	}
	return 0;
}
2021/6/30 20:04
加载中...