关于二分图最大匹配Hopcroft-Karp的算法求讲解
  • 板块学术版
  • 楼主Fnoiwzc
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/8/14 19:24
  • 上次更新2023/11/4 10:40:06
查看原帖
关于二分图最大匹配Hopcroft-Karp的算法求讲解
158424
Fnoiwzc楼主2021/8/14 19:24

这玩意变量太多了理解不了 就是每个判断不知道要干啥


bool bfs(){
  memset(dx,-1,sizeof dx);
  memset(dy,-1,sizeof dy);
  dis=INF;
  while(!q.empty()) q.pop();
  for(int i=1;i<=idx;i++){
  	if(!mat[i]){
   	q.push(i); 
    	dx[i]=0;
  	}
  }
  while(!q.empty()){
      int x=q.front();
      q.pop();
      if(dx[x]>dis) break;
      for(int i=h[x];~i;i=d[i].next){
          int v=d[i].v;
          if(dy[v]==-1){
              dy[v]=dx[x]+1;
              if(!mat[v]) dis=dy[v];
              else{
                  dx[mat[v]]=dy[v]+1;
                  q.push(mat[v]);
                  }
              }
          }
      }
      return dis!=INF;
}
bool dfs(int x){
for(int i=h[x];~i;i=d[i].next){
	int v=d[i].v;
	 if(!vis[v] and dy[v]==dx[x]+1){
	  vis[v]=true;
		if(mat[v] and dy[v]==dis) continue;
		if(!mat[v] or dfs(mat[v])){
			mat[v]=x;
			mat[x]=v;
			return 1;
		} 
	}
}
return 0;

}

2021/8/14 19:24
加载中...