Hopcroft-Karp模板学习总结

Hopcroft-Karp模板学习小结

最开始是因为做了一个题目接触到这个算法的，但是对于这个算法很多资料都只说了大概的方法：

首先从所有X的未盖点进行BFS，BFS之后对每个X节点和Y节点维护距离标号，如果Y节点是未盖点那么就找到了一条最短增广路，BFS完之后就找到了最短增广路集，随后可以直接用DFS对所有允许弧(dist[y]=dist[x]+1)进行类似于匈牙利中寻找增广路的操作，这样就可以做到O(m)的复杂度

这里还是有的地方不知道什么意思，看来只能后面慢慢理解 啦

//对于要匹配的点 分为x集合的点，和y集合的点int Mx[MAX],My[MAX];//那么这里的Mx[i]的值表示x集合中i号点的匹配点，My[j]的值就是y集合j点匹配的点int dx[MAX],dy[MAX];//这里就是bfs找增广路用的数组 对于u-->v可达就有dy[v] = dx[u] + 1int vis[MAX],dis;//辅助bool bfs(){int i ,v,u;dis = INF;queue<int>Q;memset(dx,-1,sizeof(dx));memset(dy,-1,sizeof(dy));for(i = 0; i < m ;i ++)//if(Mx[i] == -1) Q.push(i),dx[i] = 0;while(!Q.empty()){u = Q.front(); Q.pop();if(dx[u] > dis) break;for(i = head[u]; i != -1; i = edge[i].next){v = edge[i].to;if(dy[v] == -1){dy[v] = dx[u] + 1;if(My[v] == -1) dis = dy[v];else{dx[My[v]] = dy[v] + 1;Q.push(My[v]);}}}}return dis != INF;}bool dfs(int u){int v;for(int i = head[u]; i != -1; i = edge[i].next){v = edge[i].to;if(!vis[v] && dy[v] == dx[u] + 1){vis[v] = 1;if(My[v] != -1 && dy[v] == dis) continue;if(My[v] == -1 || dfs(My[v])){Mx[u] = v; My[v] = u;return true;}}}return false;}int match(){int ans = 0; memset(Mx,-1,sizeof(Mx));memset(My,-1,sizeof(My));while(bfs()){memset(vis,0,sizeof(vis));for(int u = 0; u < m; u ++)if(Mx[u] == -1 && dfs(u))//这里特别要注意，Mx[u] == -1 && dfs(u)先后顺序千万不能换，dfs之后Mx[u]就会变化ans ++;}return ans;}