匈牙利算法

匈牙利算法

鏈接: 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。。。餓了,我要去吃加餐了。

總算寫完了,畫圖真累啊。。。。。。

相關日誌