匈牙利算法

页面分类: 软件

天下维客，你可以修改的网络知识库

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

PASCAL代码实现：

var
        g:array[1..maxn,1..maxm]of boolean;
        y:array[1..maxm]of boolean;
        link:array[1..maxm]of 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[][]
 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.