计算机科学

首页 > 计算机科学

霍普克洛夫特-卡普算法

2018-08-28 09:37:13     所属分类:图算法

霍普克洛夫特-卡普算法Hopcroft Karp算法)是用来解决二分图最大匹配问题的一种算法。

在匈牙利算法中,我们每次寻找一条增广路来增加匹配集合M。可以证明,每次找增广路的复杂度是,一共需要增广次,因此总时间复杂度为。为了降低时间复杂度,在霍普克洛夫特-卡普算法中,我们在增加匹配集合M时,每次寻找多条增广路。可以证明,这样迭代次数最多为,所以,时间复杂度就降到了

该算法由John E.Hopcroft和Richard M.Karp于1973年提出,故称霍普克洛夫特-卡普算法。

program Project1;
  const maxn=1000;
  var dx,dy,mx,my,q:array1..maxnof longint;
      adj:array1..maxn,0..maxnof 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 mxi=-1
      then begin
        qff:=i;
        inc(ff);
      end;
      for i:=1 to n do dxi:=0;
      for i:=1 to m do dyi:=0;
      while rr<ff do
        begin
          u:=qrr;
          inc(rr);
          for j:=1 to adju0do
            begin
              i:=adjuj;
              if dyi=0
                then begin
                  dyi:=dxu+1;
                  if myi=-1
                    then bfs:=true
                    else begin
                      dxmyi:=dyi+1;
                      qff:=myi;
                      inc(ff);
                    end;
                end;
            end;
        end;
    end;
  function dfs(x:longint):boolean;
    var i,j:longint;
    begin
      for j:=1 to adjx0do
        begin
          i:=adjxj;
          if dyi=dxx+1
            then begin
              dyi:=0;
              if(myi=-1)or dfs(myi)
                then begin
                  mxx:=i;
                  myi:=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(adjff0);
        adjffadjff0:=rr;
      end;
    for i:=1 to n do mxi:=-1;
    for i:=1 to m do myi:=-1;
    ans:=0;
    while bfs do
      for i:=1 to n do
        if(mxi=-1)and(dfs(i))
          then inc(ans);
    writeln(ans);
  end.

相关推荐