霍普克洛夫特-卡普算法

霍普克洛夫特－卡普算法（Hopcroft Karp算法）是用來解決二分圖最大匹配問題的一種演算法。

在匈牙利算法中，我们每次寻找一条增广路来增加匹配集合M。可以证明，每次找增广路的复杂度是\mathcal{O}\left( \left|E\right| \right)，一共需要增广\mathcal{O}\left(\left|V\right|\right)次，因此总时间复杂度为\mathcal{O}\left(\left|V\right|\left|E\right|\right)。为了降低时间复杂度，在霍普克洛夫特－卡普算法中，我们在增加匹配集合M时，每次寻找多条增广路。可以证明，这样迭代次数最多为2\sqrt{\left|V\right|}，所以，时间复杂度就降到了\mathcal{O}\left(\sqrt{\left|V\right|}\left|E\right|\right)。

该算法由約翰·霍普克洛夫特和理查德·卡普于1973年提出。

program Project1;
const maxn=1000;
var dx,dy,mx,my,q:array[1..maxn]of longint;
adj:array[1..maxn,0..maxn]of longint;
n,m,e,i,j,ans,ff,rr:longint;
function bfs:boolean;
var i,u,j:longint;
begin
bfs:=false;
fillchar(q,sizeof(q),0);
rr:=1;
ff:=1;
for i:=1 to n do
if mx[i]=-1
then begin
q[ff]:=i;
inc(ff);
end;
for i:=1 to n do dx[i]:=0;
for i:=1 to m do dy[i]:=0;
while rr