Hopcroft-karp算法
该算法由John.E.Hopcroft和Richard M.Karp于1973提出，故称Hopcroft-Karp算法。
使用情形
给定一个二分图，求其最大匹配。
原理简述
在增广匹配集时，每次寻找多条增广路径，以进一步减少时间复杂度。
步骤及示例演示
dx【】、dy【】
分别表示二分图左右不顶点的距离标号
mx【】、my【】
分别表示二分图左右部顶点的距离标号
1、我们每次从所有未匹配的左部节点开始BFS，进行距离标号。
2、对于每一个队列中的左部节点X，考虑与它相邻的所有右部节点Y：
2.1、如果Y是一个未匹配的右部节点，则说明至少还存在一条增广路，用一个bool变量flag记录，以便之后增广。
2.2、否则，将Y的匹配节点加入到队列中。顺便求出距离标号。
3、当BFS结束时，
3.1、若不存在增广路（flag==false），那么算法结束；
3.2、否则，对于每一个没有匹配的左部节点X执行匈牙利算法find(x)的操作。
4、这里，find（x）过程中，只考虑边（u,v）：满足dx【u】+1==dy【v】。
与其他算法的区别于联系
Hopcroft-karp算法，相比于普通的匈牙利算法来说，由于每次是增广一系列路径，所以更快，算法复杂度降低了(n^0.5)
题目链接 点击这里
代码
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>using namespace std;const int max_n=300;
const int max_p=300;int n,p;vector<int> g[max_p+1];
// mx,my表示二分图左右顶点的匹配节点
int mx[max_p+1],my[max_n+1];
queue<int> que;
// dx,dx表示二分图左右顶点的距离标号
int dx[max_p+1],dy[max_n+1];
bool vis[max_p+1];bool find(int u)
{for(int i=0;i<g[u].size();++i){int v=g[u][i];if(!vis[v] && dy[v]==dx[u]+1){vis[v]=true;if(!my[v] || find(my[v])){mx[u]=v;my[v]=u;return true;}}}return false;
}int matching()
{// 初始化mx，my，ans；memset(mx,0,sizeof(mx));memset(my,0,sizeof(my));int ans=0;while(true){// 初始化flag，队列que，dx,dy;bool flag=false;while(!que.empty()){que.pop();}memset(dx,0,sizeof(dx));memset(dy,0,sizeof(dy));// 将没有匹配的x的编号，加入到队列中for(int i=1;i<=p;++i){if(!mx[i]){que.push(i);}}// 如果还有未曾匹配的xwhile(!que.empty()){// 选取一个未曾匹配的xint u=que.front();que.pop();for(int i=0;i<g[u].size();++i){int v=g[u][i];//如果y距离未曾设置if(!dy[v]){// 设置距离判断条件,dy[v]是dx[u]的下一个匹配点dy[v]=dx[u]+1;if(my[v]){dx[ my[v] ] = dy[v] +1;que.push(my[v]);}else{flag=true;}}}}if(!flag){break;}memset(vis,0,sizeof(vis));for(int i=1;i<=p;++i){if(!mx[i] && find(i)){ans++;}}}return ans;
}int main()
{int T;scanf("%d",&T);while(T--){scanf("%d %d",&p,&n);for(int i=1;i<=p;++i){int cnt,k;scanf("%d",&cnt);for(int j=0;j<cnt;++j){scanf("%d",&k);g[i].push_back(k);}}int ans=matching();if(ans==p){printf("YES\n");}else{printf("NO\n");}// 记得清空vector容器// 第一次写的时候，忘记清空容器了，导致发生了错误，又找不到算法的问题// 花费了很多时间for(int i=1;i<=n;++i){g[i].clear();}}return 0;
}