霍普克洛夫特-卡普算法

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

在匈牙利算法中，我们每次寻找一条增广路来增加匹配集合M。可以证明，每次找增广路的复杂度是${\displaystyle {\mathcal {O}}\left(\left|E\right|\right)}$，一共需要增广${\displaystyle {\mathcal {O}}\left(\left|V\right|\right)}$次，因此总时间复杂度为${\displaystyle {\mathcal {O}}\left(\left|V\right|\left|E\right|\right)}$。为了降低时间复杂度，在霍普克洛夫特－卡普算法中，我们在增加匹配集合M时，每次寻找多条增广路。可以证明，这样迭代次数最多为${\displaystyle 2{\sqrt {\left|V\right|}}}$，所以，时间复杂度就降到了${\displaystyle {\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<ff do  begin  u:=q[rr];  inc(rr);  for j:=1 to adj[u][0]do  begin  i:=adj[u][j];  if dy[i]=0  then begin  dy[i]:=dx[u]+1;  if my[i]=-1  then bfs:=true  else begin  dx[my[i]]:=dy[i]+1;  q[ff]:=my[i];  inc(ff);  end;  end;  end;  end;  end;  function dfs(x:longint):boolean;  var i,j:longint;  begin  for j:=1 to adj[x][0]do  begin  i:=adj[x][j];  if dy[i]=dx[x]+1  then begin  dy[i]:=0;  if(my[i]=-1)or dfs(my[i])  then begin  mx[x]:=i;  my[i]:=x;  exit(true);  end;  end;  end;  exit(false);  end;  begin  readln(n,m,e);  for i:=1 to e do  begin  readln(ff,rr);  inc(adj[ff][0]);  adj[ff][adj[ff][0]]:=rr;  end;  for i:=1 to n do mx[i]:=-1;  for i:=1 to m do my[i]:=-1;  ans:=0;  while bfs do  for i:=1 to n do  if(mx[i]=-1)and(dfs(i))  then inc(ans);  writeln(ans);  end.