一、匈牙利算法介紹

匈牙利算法（Hungarian algorithm）主要用于解決一些與二分圖匹配有關(guān)的問(wèn)題，所以我們先來(lái)了解一下二分圖。

二分圖（Bipartite graph）是一類特殊的圖，它可以被劃分為兩個(gè)部分，每個(gè)部分內(nèi)的點(diǎn)互不相連。下圖是典型的二分圖。

可以看到，在上面的二分圖中，每條邊的端點(diǎn)都分別處于點(diǎn)集X和Y中。匈牙利算法主要用來(lái)解決兩個(gè)問(wèn)題：求二分圖的最大匹配數(shù)和最小點(diǎn)覆蓋數(shù)。

這么說(shuō)起來(lái)過(guò)于抽象了，我們現(xiàn)在從實(shí)際問(wèn)題出發(fā)。

二、最大匹配問(wèn)題

看完上面講的，相信讀者會(huì)覺得云里霧里的：這是啥？這有啥用？所以我們把這張二分圖稍微做點(diǎn)手腳，變成下面這樣：

現(xiàn)在Boys和Girls分別是兩個(gè)點(diǎn)集，里面的點(diǎn)分別是男生和女生，邊表示他們之間存在“曖昧關(guān)系"。最大匹配問(wèn)題相當(dāng)于，假如你是紅娘，可以撮合任何一對(duì)有曖昧關(guān)系的男女，那么你最多能成全多少對(duì)情侶？（數(shù)學(xué)表述：在二分圖中最多能找到多少條沒有公共端點(diǎn)的邊）

現(xiàn)在我們來(lái)看看匈牙利算法是怎么運(yùn)作的：

我們從B1看起（男女平等，從女生這邊看起也是可以的），他與G2有曖昧，那我們就先暫時(shí)把他與G2連接（注意這時(shí)只是你作為一個(gè)紅娘在紙上構(gòu)想，你沒有真正行動(dòng)，此時(shí)的安排都是暫時(shí)的）。

來(lái)看B2，B2也喜歡G2，這時(shí)G2已經(jīng)“名花有主”了（雖然只是我們?cè)O(shè)想的），那怎么辦呢？我們倒回去看G2目前被安排的男友，是B1，B1有沒有別的選項(xiàng)呢？有，G4，G4還沒有被安排，那我們就給B1安排上G4。

然后B3，B3直接配上G1就好了，這沒什么問(wèn)題。至于B4，他只鐘情于G4，G4目前配的是B1。B1除了G4還可以選G2，但是呢，如果B1選了G2，G2的原配B2就沒得選了。我們繞了一大圈，發(fā)現(xiàn)B4只能注定單身了，可憐。（其實(shí)從來(lái)沒被考慮過(guò)的G3更可憐）

這就是匈牙利算法的流程，至于具體實(shí)現(xiàn)，我們來(lái)看看代碼：

int M, N;            //M, N分別表示左、右側(cè)集合的元素?cái)?shù)量
int Map[MAXM][MAXN]; //鄰接矩陣存圖
int p[MAXN];         //記錄當(dāng)前右側(cè)元素所對(duì)應(yīng)的左側(cè)元素
bool vis[MAXN];      //記錄右側(cè)元素是否已被訪問(wèn)過(guò)
bool match(int i)
{
    for (int j = 1; j <= N; ++j)
        if (Map[i][j] && !vis[j]) //有邊且未訪問(wèn)
        {
            vis[j] = true;                 //記錄狀態(tài)為訪問(wèn)過(guò)
            if (p[j] == 0 || match(p[j])) //如果暫無(wú)匹配，或者原來(lái)匹配的左側(cè)元素可以找到新的匹配
            {
                p[j] = i;    //當(dāng)前左側(cè)元素成為當(dāng)前右側(cè)元素的新匹配
                return true; //返回匹配成功
            }
        }
    return false; //循環(huán)結(jié)束，仍未找到匹配，返回匹配失敗
}
int Hungarian()
{
    int cnt = 0;
    for (int i = 1; i <= M; ++i)
    {
        memset(vis, 0, sizeof(vis)); //重置vis數(shù)組
        if (match(i))
            cnt++;
    }
    return cnt;
}

其實(shí)流程跟我們上面描述的是一致的。注意這里使用了一個(gè)遞歸的技巧，我們不斷往下遞歸，嘗試尋找合適的匹配。

三、最小點(diǎn)覆蓋問(wèn)題

另外一個(gè)關(guān)于二分圖的問(wèn)題是求最小點(diǎn)覆蓋：我們想找到最少的一些點(diǎn)，使二分圖所有的邊都至少有一個(gè)端點(diǎn)在這些點(diǎn)之中。倒過(guò)來(lái)說(shuō)就是，刪除包含這些點(diǎn)的邊，可以刪掉所有邊。

這為什么用匈牙利算法可以解決呢？你如果以為我要長(zhǎng)篇大論很久就錯(cuò)了，我們只需要一個(gè)定理：

（König定理）

一個(gè)二分圖中的最大匹配數(shù)等于這個(gè)圖中的最小點(diǎn)覆蓋數(shù)。

好了，本節(jié)可以結(jié)束了，我們不是搞數(shù)學(xué)的，不需要證明。但是提供一個(gè)直觀地找最小覆蓋點(diǎn)集的方法：看題圖，從左側(cè)一個(gè)未匹配成功的點(diǎn)出發(fā)，走一趟匈牙利算法的流程（即紫色的箭頭），所有左側(cè)未經(jīng)過(guò)的點(diǎn)，和右側(cè)經(jīng)過(guò)的點(diǎn)，即組成最小點(diǎn)覆蓋。（即圖中的B3、G2、G4）

對(duì)于每個(gè)左部節(jié)點(diǎn)，尋找增廣路最多遍歷整張二分圖一次，因此，該算法時(shí)間復(fù)雜度為O(MN)

四、匈牙利算法的應(yīng)用

一些題目，乍一看與上面這個(gè)男女配對(duì)的問(wèn)題沒有任何相似點(diǎn)，其實(shí)都可以用匈牙利算法。例如：

4.1、（洛谷P1129） [ZJOI2007]矩陣游戲

題目描述

小Q是一個(gè)非常聰明的孩子，除了國(guó)際象棋，他還很喜歡玩一個(gè)電腦益智游戲――矩陣游戲。矩陣游戲在一個(gè)$ N× N $ 黑白方陣進(jìn)行（如同國(guó)際象棋一般，只是顏色是隨意的）。每次可以對(duì)該矩陣進(jìn)行兩種操作：
行交換操作：選擇矩陣的任意兩行，交換這兩行（即交換對(duì)應(yīng)格子的顏色）
列交換操作：選擇矩陣的任意兩列，交換這兩列（即交換對(duì)應(yīng)格子的顏色）
游戲的目標(biāo)，即通過(guò)若干次操作，使得方陣的主對(duì)角線(左上角到右下角的連線)上的格子均為黑色。
對(duì)于某些關(guān)卡，小Q百思不得其解，以致他開始懷疑這些關(guān)卡是不是根本就是無(wú)解的！于是小Q決定寫一個(gè)程序來(lái)判斷這些關(guān)卡是否有解。
輸入格式
第一行包含一個(gè)整數(shù)T，表示數(shù)據(jù)的組數(shù)。
接下來(lái)包含T組數(shù)據(jù)，每組數(shù)據(jù)第一行為一個(gè)整數(shù)N，表示方陣的大??；接下來(lái)N行為一個(gè) $ N× N $的01矩陣（0表示白色，1表示黑色）。
輸出格式
包含T行。對(duì)于每一組數(shù)據(jù)，如果該關(guān)卡有解，輸出一行Yes；否則輸出一行No。

我們把矩陣轉(zhuǎn)化為二分圖（左側(cè)集合代表各行，右側(cè)集合代表各列，某位置為1則該行和該列之間有邊）。我們想進(jìn)行一系列交換操作，使得X1連上Y1，X2連上Y2，……

大家可以想象，所謂的交換，是不是可以等價(jià)為重命名？我們可以在保持當(dāng)前二分圖結(jié)構(gòu)不變的情況下，把右側(cè)點(diǎn)的編號(hào)進(jìn)行改變，這與交換的效果是一樣的。

所以想讓X1、X2...與Y1、Y2...一一對(duì)應(yīng)，其實(shí)只需要原圖最大匹配數(shù)為4就行了。（這與組合數(shù)學(xué)中相異代表系的概念相合）。代碼如下：

#include <cstdio>
#include <cstring>
int Map[205][205], p[205], vis[205], N, T;
bool match(int i){
    for (int j = 1; j <= N; ++j){
        if (Map[i][j] && !vis[j]){
            vis[j] = 1;
            if (p[j] == 0 || match(p[j])){
                p[j] = i;
                return true;
            }
        }
    }
    return false;
}
int Hungarian(){
    int cnt = 0;
    for (int i = 1; i <= N; ++i){
        memset(vis, 0, sizeof(vis));
        if (match(i))
            cnt++;
    }
    return cnt;
}
int main(){
    scanf("%d", &T);
    while (T--){
        scanf("%d", &N);
        memset(p, 0, sizeof(p));
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= N; ++j)
                scanf("%d", &Map[i][j]);
        puts(Hungarian() == N ? "Yes" : "No");
    }
    return 0;
}

4.2、（vijos1204） CoVH之柯南開鎖

面對(duì)OIBH組織的囂張氣焰, 柯南決定深入牛棚, 一探虛實(shí).
他經(jīng)過(guò)深思熟慮, 決定從OIBH組織大門進(jìn)入...........
OIBH組織的大門有一個(gè)很神奇的鎖.
鎖是由M*N個(gè)格子組成, 其中某些格子凸起(灰色的格子). 每一次操作可以把某一行或某一列的格子給按下去.

如果柯南能在組織限定的次數(shù)內(nèi)將所有格子都按下去, 那么他就能夠進(jìn)入總部. 但是OIBH組織不是吃素的, 他們的限定次數(shù)恰是最少次數(shù).

請(qǐng)您幫助柯南計(jì)算出開給定的鎖所需的最少次數(shù).

讀入/Input：

第一行 兩個(gè)不超過(guò)100的正整數(shù)N, M表示矩陣的長(zhǎng)和寬
以下N行 每行M個(gè)數(shù) 非0即1 1為凸起方格

輸出/Output：

一個(gè)整數(shù) 所需最少次數(shù)

如果我們把樣例的矩陣，轉(zhuǎn)化為二分圖的形式，是這樣的：

按下一行或一列，其實(shí)就是刪掉與某個(gè)點(diǎn)相連的所有邊?，F(xiàn)在要求最少的操作次數(shù)，想想看，這不就是求最小點(diǎn)覆蓋數(shù)嗎？所以直接套匈牙利算法即可。代碼略。

4.3、（TYVJ P1035） 棋盤覆蓋

描述 Description
給出一張nn(n<=100)的國(guó)際象棋棋盤，其中被刪除了一些點(diǎn)，問(wèn)可以使用多少12的多米諾骨牌進(jìn)行掩蓋。
輸入格式 Input Format
第一行為n，m（表示有m個(gè)刪除的格子）
第二行到m+1行為x,y，分別表示刪除格子所在的位置
x為第x行
y為第y列
輸出格式 Output Format
一個(gè)數(shù)，即最大覆蓋格數(shù)

經(jīng)典的多米諾覆蓋問(wèn)題大家都很熟悉，我們把棋盤染色，每個(gè)多米諾骨牌恰好覆蓋一個(gè)白格和一個(gè)黑格（這里為了美觀染成了其他顏色，下面仍將其稱作黑格）。

我們刪除了一些格子：

現(xiàn)在要求多米諾骨牌最大覆蓋數(shù)。

你可能已經(jīng)看出來(lái)了，我們?cè)谌旧螅诟窈桶赘窨梢詷?gòu)成一個(gè)二分圖，每個(gè)白格都只和黑格相連，每個(gè)黑格也只和白格相連。在給所有黑格和白格編號(hào)后，我們把每個(gè)未刪除的格子都與它上下左右緊鄰的未刪除的格子相連。很顯然，這張二分圖的最大匹配數(shù)，就是我們能放下最多的多米諾骨牌數(shù)。注意因?yàn)閿?shù)據(jù)范圍較大，要用鄰接表存圖。

#include <cstdio>
#include <cstring>
#define MAXN 5500
struct Edges
{
    int to, next;
} edges[MAXN * 8];
int Map[105][105], head[MAXN], p[MAXN], vis[MAXN], N, cnt_edge;
inline int add(int from, int to)
{
    edges[++cnt_edge].next = head[from];
    head[from] = cnt_edge;
    edges[cnt_edge].to = to;
}
inline int trans(int i, int j, int n) //把坐標(biāo)轉(zhuǎn)化為編號(hào)
{
    return ((i - 1) * n + j + 1) / 2;
}
bool match(int i)
{
    for (int e = head[i]; e; e = edges[e].next)
    {
        int j = edges[e].to;
        if (!vis[j])
        {
            vis[j] = true;
            if (p[j] == 0 || match(p[j]))
            {
                p[j] = i;
                return true;
            }
        }
    }
    return false;
}
int Hungarian()
{
    int cnt = 0;
    for (int i = 1; i <= N; ++i)
    {
        memset(vis, 0, sizeof(vis));
        if (match(i))
            cnt++;
    }
    return cnt;
}
int main()
{
    int n, m, x, y;
    scanf("%d%d", &n, &m);
    N = (n * n + 1) / 2;
    memset(Map, -1, sizeof(Map));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            Map[i][j] = 0;
    for (int i = 0; i < m; ++i)
    {
        scanf("%d%d", &x, &y);
        Map[x][y] = -1;
    }
    for (int i = 1; i <= n; i++)
        for (int j = i % 2 ? 1 : 2; j <= n; j += 2)
            if (Map[i][j] == 0)
            {
                if (Map[i + 1][j] != -1)
                    add(trans(i, j, n), trans(i + 1, j, n));
                if (Map[i][j + 1] != -1)
                    add(trans(i, j, n), trans(i, j + 1, n));
                if (Map[i - 1][j] != -1)
                    add(trans(i, j, n), trans(i - 1, j, n));
                if (Map[i][j - 1] != -1)
                    add(trans(i, j, n), trans(i, j - 1, n));
            }
    printf("%d\n", Hungarian());
    return 0;
}

以上就是詳解C++實(shí)現(xiàn)匈牙利算法的詳細(xì)內(nèi)容，更多關(guān)于C++匈牙利算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論