匈牙利算法

 本文转自大牛博客：http://www.byvoid.com/blog/hungary/

这是一种用增广路求二分图最大匹配的算法。它由匈牙利数学家Edmonds于1965年提出，因而得名。 定义 未盖点：设Vi是图G的一个顶点，假设Vi 不与随意一条属于匹配M的边相关联，就称Vi 是一个未盖点。

交错路：设P是图G的一条路，假设P的随意两条相邻的边一定是一条属于M而还有一条不属于M，就称P是一条交错路。

可增广路：两个端点都是未盖点的交错路叫做可增广路。

流程图

伪代码：

bool 寻找从k出发的相应项出的可增广路<br />{<br /> while (从邻接表中列举k能关联到顶点j)<br /> {<br /> if (j不在增广路上)<br /> {<br /> 把j增加增广路;<br /> if (j是未盖点 或者 从j的相应项出发有可增广路)<br /> {<br /> 改动j的相应项为k;<br /> 则从k的相应项出有可增广路,返回true;<br /> }<br /> }<br /> }<br /> 则从k的相应项出没有可增广路,返回false;<br />}</p> <p>void 匈牙利hungary()<br />{<br /> for i->1 to n<br /> {<br /> if (则从i的相应项出有可增广路)<br /> 匹配数++;<br /> }<br /> 输出 匹配数;<br />}

演示：

C实现（作者BYVoid）

#include <stdio.h><br />#include <string.h><br />#define MAX 102</p> <p>long n,n1,match;<br />long adjl[MAX][MAX];<br />long mat[MAX];<br />bool used[MAX];</p> <p>FILE *fi,*fo;</p> <p>void readfile()<br />{<br /> fi=fopen(“flyer.in”,”r”);<br /> fo=fopen(“flyer.out”,”w”);<br /> fscanf(fi,”%ld%ld”,&n,&n1);<br /> long a,b;<br /> while (fscanf(fi,”%ld%ld”,&a,&b)!=EOF)<br /> adjl[a][ ++adjl[a][0] ]=b;<br /> match=0;<br />}</p> <p>bool crosspath(long k)<br />{<br /> for (long i=1;i<=adjl[k][0];i++)<br /> {<br /> long j=adjl[k][i];<br /> if (!used[j])<br /> {<br /> used[j]=true;<br /> if (mat[j]==0 || crosspath(mat[j]))<br /> {<br /> mat[j]=k;<br /> return true;<br /> }<br /> }<br /> }<br /> return false;<br />}</p> <p>void hungary()<br />{<br /> for (long i=1;i<=n1;i++)<br /> {<br /> if (crosspath(i))<br /> match++;<br /> memset(used,0,sizeof(used));<br /> }<br />}</p> <p>void print()<br />{<br /> fprintf(fo,”%ld”,match);<br /> fclose(fi);<br /> fclose(fo);<br />}</p> <p>int main()<br />{<br /> readfile();<br /> hungary();<br /> print();<br /> return 0;<br />}

Pascal实现（作者魂牛）

var<br /> a:array[1..1000,1..1000] of boolean;<br /> b:array[1..1000] of longint;<br /> c:array[1..1000] of boolean;<br /> n,k,i,x,y,ans,m:longint;</p> <p>function path(x:longint):boolean;<br />var<br /> i:longint;<br />begin<br /> for i:=1 to n do<br /> if a[x,i] and not c[i] then<br /> begin<br /> c[i]:=true;<br /> if (b[i]=0) or path(b[i]) then<br /> begin<br /> b[i]:=x;<br /> exit(true);<br /> end;<br /> end;<br /> exit(false);<br />end;</p> <p>procedure hungary;<br />var<br /> i:longint;<br />begin<br /> fillchar(b,sizeof(b),0);<br /> for i:=1 to m do<br /> begin<br /> fillchar(c,sizeof(c),0);<br /> if path(i) then inc(ans);<br /> end;<br />end;</p> <p>begin<br /> fillchar(a,sizeof(a),0);<br /> readln(m,n,k);<br /> for i:=1 to k do<br /> begin<br /> readln(x,y);<br /> a[x,y]:=true;<br /> end;<br /> ans:=0;<br /> hungary;<br /> writeln(ans);<br />end.

ps:近期由于比赛，须要用到二分图，图论这东西好多要好好学的。