Hopcroft-Karp算法
该算法由John.E.Hopcroft和Richard M.Karp于1973提出，故称Hopcroft-Karp算法。
原理
为了降低时间复杂度，可以在增广匹配集合M时，每次寻找多条增广路径。这样就可以进一步降低时间复杂度，可以证明，算法的时间复杂度可以到达O（n^0.5*m），虽然优化不了多少，但在实际应用时，效果还是很明显的。
基本算法
该算法主要是对匈牙利算法的优化，在寻找增广路径的时候同时寻找多条不相交的增广路径，形成极大增广路径集，然后对极大增广路径集进行增广。在寻找 增广路径集的每个阶段，找到的增广路径集都具有相同的长度，且随着算法的进行，增广路径的长度不断的扩大。可以证明，最多增广n^0.5次就可以得到最大 匹配。
算法流程
（1）从G=(X,Y;E)中取一个初始匹配。
（2）若X中的所有顶点都被M匹配，则表明M为一个完美匹配，返回；否则，以所有未匹配顶点为源点进行一次BFS，标记各个点到源点的距离。
（3）在满足dis[v] = dis[u] + 1的边集<v,u>中，从X中找到一个未被M匹配的顶点x0，记S = {x0}，T = ￠。
（4）若N（S） = T，则表明当前已经无法得到更大匹配，返回；否则取一y0∈N(S) - 。
（5）若y0已经被M匹配则转步骤（6），否则做一条x0->y0的M-增广路径P（x0,y0）,取M = M△P（x0,y0）。
（6）由于y已经被M匹配，所以M中存在一条边（y0,z0）去S = S∪ {z0}，T = T∪{y0}，转步骤（2）。
算法具体时间与分析
在寻找增广路径中可以对X中的每个未匹配的顶点进行BFS，BFS时对每个顶点维护一个距离编号dx[nx],dy[ny]，如果某个Y中的节点为 未匹配点，则找到一条增广路径。BFS结束后找到了增广路径集。然后利用DFS与匈牙利算法类似的方法对每条增广路进行增广，这样就可以找到最大匹配。
Description
Input
Output
Sample Input
Sample Output
#include<stdio.h> #include<queue> #include<iostream> #include<string.h> #include<math.h> using namespace std; #define eps 1e-6 const int MAXN=3005; const int INF=1<<28; int g[MAXN][MAXN],Mx[MAXN],My[MAXN],Nx,Ny; int dx[MAXN],dy[MAXN],dis; bool vst[MAXN]; struct Node1 { int x,y,s; }guests[MAXN]; struct Node2 { int x,y; }um[MAXN]; double distance(Node1 a,Node2 b) { double x=a.x-b.x; double y=a.y-b.y; return sqrt(x*x+y*y); } bool searchP() { queue<int>Q; dis=INF; memset(dx,-1,sizeof(dx)); memset(dy,-1,sizeof(dy)); for(int i=0;i<Nx;i++) if(Mx[i]==-1) { Q.push(i); dx[i]=0; } while(!Q.empty()) { int u=Q.front(); Q.pop(); if(dx[u]>dis) break; for(int v=0;v<Ny;v++) if(g[u][v]&&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) { for(int v=0;v<Ny;v++) if(!vst[v]&&g[u][v]&&dy[v]==dx[u]+1) { vst[v]=1; if(My[v]!=-1&&dy[v]==dis) continue; if(My[v]==-1||DFS(My[v])) { My[v]=u; Mx[u]=v; return 1; } } return 0; } int MaxMatch() { int res=0; memset(Mx,-1,sizeof(Mx)); memset(My,-1,sizeof(My)); while(searchP()) { memset(vst,0,sizeof(vst)); for(int i=0;i<Nx;i++) if(Mx[i]==-1&&DFS(i)) res++; } return res; } int main(){ int n,m,t,i,j; int T,iCase=0; scanf("%d",&T); while(T--) { iCase++; scanf("%d",&t); scanf("%d",&m); for(i=0;i<m;i++) scanf("%d%d%d",&guests[i].x,&guests[i].y,&guests[i].s); scanf("%d",&n); for(i=0;i<n;i++) scanf("%d%d",&um[i].x,&um[i].y); Nx=m;Ny=n; memset(g,0,sizeof(g)); for(i=0;i<m;i++) { for(j=0;j<n;j++) { if(distance(guests[i],um[j])/guests[i].s-t<eps) { g[i][j]=1; } } } printf("Scenario #%d:\n%d\n\n",iCase,MaxMatch()); } return 0; }
二分图------》Hopcroft-Karp算法 hdu2389
原文：http://www.cnblogs.com/13224ACMer/p/5252375.html