二分図マッチングのハンガリーアルゴリズムと二分図マッチングのいくつかの問題型

まずハンガリーアルゴリズムを紹介します.
1つの二分図に拡張路(インターリーブ路)がある場合、マッチング数を1回に1つ以上反転させることができる.
ハンガリーのアルゴリズムは、拡張路が求められないまで、すなわち最大マッチングを求めることです.
プログラム実装:

program hungray;
var map:array[1..500,1..500]of byte;//   
    r,c,n,k,i,ans:longint;
    start:array[1..500]of boolean;//         ，                ，       
    resul:array[1..500]of longint;//    ，    
function dfs(x:longint):boolean;//   
var i:longint;
begin
 for i:=1 to n do
  if (map[x,i]=1)and(not start[i]) then
   begin
    start[i]:=true;//     ，         ，    。    
    if (resul[i]=0)or(dfs(resul[i])) then//         ，         ，    
     begin
      resul[i]:=x;//     
      dfs:=true;
      exit;//          
     end;
   end;
 dfs:=false;
end;
begin
 read(n,k);
 for i:=1 to k do
  begin
   read(r,c);
   map[r,c]:=1;
  end;
 ans:=0;
 for i:=1 to n do//  X    
  begin
   fillchar(start,sizeof(start),false);
   if dfs(i) then ans:=ans+1;
  end;
 write(ans);
end.

いくつかの重要な応用:
①最小点セットオーバーライド問題:最小点オーバーライド=最大一致
通常、グリッド内の行と列を2つのポイントセットに分割する必要があります.ある行の列にポイントがある場合は、エッジ(エッジとみなされます)を1つ接続し、最大マッチングを行う必要があります.
②最小パスオーバーライド:出度入度を一致させる(2点接続、2点接続)