匈牙利算法

维基百科，自由的百科全书

匈牙利算法是用来解决二分图最大匹配问题的经典算法。

PASCAL代码实现：

var
       g:array[1..maxn,1..maxm]of boolean;
       y:array[1..maxm]of boolean;
       link:array[1..maxm]of longint;
       n,m,ans:longint;
function find(v:longint):boolean;
var i:longint;
begin
       for i:=1 to m do
        if g[v,i] and (not y[i]) then
               begin
                y[i]:=true;
                       if (link[i]=0)or find(link[i]) then
                       begin
                        link[i]:=v;
                               find:=true;
                               exit;
                       end;
               end;
       find:=false;
end;
begin
//read the graph into array g[][] {无向，从n向 m连边:g[n,m](not g[m,n])}
fillchar(link,sizeof(link),0);
ans:=0;
for i:=1 to n do
       begin
               fillchar(y,sizeof(y),0);
               if find(i) then inc(ans);
       end;
//now then ans stores the max match
end.