1匈牙利算法.doc

匈牙利算法： X部 Y部 X1 Y1 X2 Y2 X3 Y3 X4 Y4 X5 Y5 Y6 （图1）1 如图1，是一个二分图（或偶图）2 任意找一初始匹配，比如：图2（X1Y1，X4Y2，X5Y4）实线所示3寻找一条可增广道路： 该道路的2个端点（起点、终点）是未匹配点 （非饱和点），而且道路是由非匹配边和匹配边 虚线和实线交错出现组成（又称交互道）。如图2：尖头所示（X2Y1-Y1X1-X1Y2-Y2X4-X4Y4-Y4X5-X5Y5）4调整匹配边：把道路上的非匹配边改为匹配边， 匹配边改为非匹配边。这样就可以使匹配边增加 一条（因为增广道路的边为奇数，非匹配边比 匹配边多一条）如图3 （图2）5继续寻找可增广道路，调整，直到不存在可增广道路为止。时间复杂度：O（|V|E|） （图3）匈牙利算法：var map:array1.1000,1.1000 of boolean;from:array1.1000 of integer;used:array1.1000 of boolean;n,m,i,j,count:integer;function change(x:integer):boolean;由X部的顶点x出发，确定一条增广路径var i:integer; begin for i:=1 to m do if mapx,i and not usedi then begin usedi:=true;Y部路径上的点设封锁标志 if (fromi=0) or change(fromi) then fromi=0表示已经找到增广路径；若fromi0，表示已匹配了一条实边，需要回到X部的fromi点，确定路径上的下一个点；虚实交错！ begin fromi:=x; 确定一条实边change:=true; exit;end;end;change:=false;已无增广路径end;begin主程序assign(input,input.txt); reset(input);read(n,m);读如二分图，X部与Y部的顶点数repeatread(i,j);if i=0 then break;mapi,j:=true;X部顶点I与Y部顶点J相连until false;close(input);assign(output,output.txt); rewrite(output);count:=0;for i:=1 to n do 枚举X部的顶点beginfillchar(used,sizeof(used),0);每次都冲零！if change(i) then inc(count);若找到一条增广路径，则匹配数加1end;writeln(count);close(output);end.mapi,j记录x中的i和y中j是否可匹配，fromi记录y中的已盖点i连着x中的那个点，如果i是未盖点，则fromi=0，另外在寻找可增广轨时不能有重复，所以用usedi记录x中的i是否被访问过。从x中一未盖点出发，通过交错轨（匹配边和非匹