關于二分圖最大比對--匈牙利算法的了解

二分圖：圖的點可以分為兩個集合，記為S,T，其中每個集合的點之間不存在邊

二分圖的最大比對：每個點都隻能用一次的情況，能夠保留最多的邊的條數

一般求最大比對采用的匈牙利的算法，下面介紹以下匈牙利算法

-----------------------------------------匈牙利算法-----------------------------------------------------------------------

匈牙利算法的複雜度是O(ve)，v是點的個數，e是邊的個數，匈牙利算法的關鍵在于尋找增廣路。

那麼我就先科普一下什麼是增廣路：

增廣路主要有以下幾條性質：

1.增廣路經上的邊數一定是奇數個

2.增廣路經上的邊連結的兩個點一定不在同一個集合中

3.增廣路徑上沒有重複的點

4.增廣路經的起點和終點所連的邊一定不在目前的比對中。

5.可以通過翻轉增廣路得到更比對

那麼每次找到增廣路就可以将最大比對數+1了，然後記錄新的比對

代碼如下：

因為是深搜是以我會具體将一下算法實作的思路（畢竟dfs不是那麼直覺^_^）

int used[MAX];  
int linker[MAX];  
  
bool dfs ( int u )  
{  
    for ( int i = head[u] ; ~i ; i = e[i].next )  
    {  
        int v = e[i].v;  
        if ( used[v] ) continue;  
        used[v] = 1;  
        if ( linker[v] == -1 || dfs ( linker[v] ) )  
        {  
            linker[v] = u;  
            return true;  
        }   
    }  
    return false;  
}  
  
int hungary ( )  
{  
    int res = 0;  
    memset ( linker , -1 , sizeof ( linker ) );  
    for ( int i = 1 ; i <= n ; i++ )  
    {  
        memset ( used , 0 , sizeof ( used ) );  
        if ( dfs ( i ) ) res++;  
    }
    return res;
}

實作方法進行講解：
首先我們将二分圖的兩個集合定義為左集和右集，定義used[i]數組标記右集當中的點是否被使用，防止在查找增廣路的時候，右集中的點被多次使用，linker[i]數組記錄右集中點i
目前比對到的左集中的點.
那麼基本的定義清晰了，
1.我們的做法就是枚舉左集中的點作為增廣路的起點，然後查找與它之間存在邊的右集中的點，最開始所有的點都沒有比對，那麼直接找到了一個沒有比對
到任何點的右集中的點，那麼目前增廣路的長度為1，直接轉換，因為增廣路是奇數，且兩端的邊為不在比對中的邊，所有翻轉後的最大比對會加1。
2.然後枚舉到第二個點進行比對，如果它也直接找到沒有比對的右集中的點那麼同1，如果找到和1中初始點找到的相同的點，那麼進行深搜，找到1，去找另一個能夠比對的點，
也就是在深搜的過程中，利用linker數組在增廣路經中加了一條目前比對中存在的邊。然後翻轉的時候，是比對的邊去掉，不是比對的邊加上，比對數+1，而且依舊滿足比對的
性質
3.直到不存在增廣路的時候算法結束，因為算法的最大比對是n，是以增廣路能夠查找到的次數不會超過n次，因為最大比對不會超過n