匈牙利算法
本文正體字版由OpenCC轉換
匈牙利算法
鏈接： USACO 4.2.2 The Perfect Stall 完美的牛欄 stall4這是一種用增廣路求二分圖最大匹配的算法。它由匈牙利數學家Edmonds於1965年提出，因而得名。 定義 未蓋點：設Vi是圖G的一個頂點，如果Vi 不與任意一條屬於匹配M的邊相關聯，就稱Vi 是一個未蓋點。
交錯路：設P是圖G的一條路，如果P的任意兩條相鄰的邊一定是一條屬於M而另一條不屬於M，就稱P是一條交錯路。
可增廣路：兩個端點都是未蓋點的交錯路叫做可增廣路。 
流程圖
僞代碼：
bool 尋找從k出發的對應項出的可增廣路
{
while (從鄰接表中列舉k能關聯到頂點j)
{
if (j不在增廣路上)
{
把j加入增廣路;
if (j是未蓋點 或者 從j的對應項出發有可增廣路)
{
修改j的對應項爲k;
則從k的對應項出有可增廣路,返回true;
}
}
}
則從k的對應項出沒有可增廣路,返回false;
}
void 匈牙利hungary()
{
for i->1 to n
{
if (則從i的對應項出有可增廣路)
匹配數++;
}
輸出 匹配數;
}
演示
C實現(作者BYVoid)
#include <stdio.h>
#include <string.h>
#define MAX 102
long n,n1,match;
long adjl[MAX][MAX];
long mat[MAX];
bool used[MAX];
FILE *fi,*fo;
void readfile()
{
fi=fopen("flyer.in","r");
fo=fopen("flyer.out","w");
fscanf(fi,"%ld%ld",&n,&n1);
long a,b;
while (fscanf(fi,"%ld%ld",&a,&b)!=EOF)
adjl[a][ ++adjl[a][0] ]=b;
match=0;
}
bool crosspath(long k)
{
for (long i=1;i<=adjl[k][0];i++)
{
long j=adjl[k][i];
if (!used[j])
{
used[j]=true;
if (mat[j]==0 || crosspath(mat[j]))
{
mat[j]=k;
return true;
}
}
}
return false;
}
void hungary()
{
for (long i=1;i<=n1;i++)
{
if (crosspath(i))
match++;
memset(used,0,sizeof(used));
}
}
void print()
{
fprintf(fo,"%ld",match);
fclose(fi);
fclose(fo);
}
int main()
{
readfile();
hungary();
print();
return 0;
}
Pascal實現(作者魂牛)
var
a:array[1..1000,1..1000] of boolean;
b:array[1..1000] of longint;
c:array[1..1000] of boolean;
n,k,i,x,y,ans,m:longint;
function path(x:longint):boolean;
var
i:longint;
begin
for i:=1 to n do
if a[x,i] and not c[i] then
begin
c[i]:=true;
if (b[i]=0) or path(b[i]) then
begin
b[i]:=x;
exit(true);
end;
end;
exit(false);
end;
procedure hungary;
var
i:longint;
begin
fillchar(b,sizeof(b),0);
for i:=1 to m do
begin
fillchar(c,sizeof(c),0);
if path(i) then inc(ans);
end;
end;
begin
fillchar(a,sizeof(a),0);
readln(m,n,k);
for i:=1 to k do
begin
readln(x,y);
a[x,y]:=true;
end;
ans:=0;
hungary;
writeln(ans);
end.
鳴謝：魂牛
一點廢話
在魂牛的幫助下，我終於正確得寫出了了匈牙利算法，原來它這麼好寫啊。感謝魂牛支持!
另外，hungary這個詞容易讓我聯想到hungry。。。餓了，我要去喫加餐了。
總算寫完了，畫圖真累啊。。。。。。
上次修改時間 2017-05-22