C語言[二分圖最大匹配] 匈牙利算法

const int INF = 0x3f3f3f3f;
const int MAXN=510;
int uN,vN;//u,v數目
int g[MAXN][MAXN];//構圖
int link[MAXN];   //link[v]=u表示右邊對左邊的匹配
bool used[MAXN];//是否訪問過
bool dfs(int u)//從左邊開始找增廣路徑
{
    int v;
    for(v=0;v<vN;v++)//右邊頂點編號從0開始
    {
        if(g[u][v]&&!used[v])  //如果存在通路,且從u開始搜索時該點沒訪問過
        {
            used[v]=true;
            if(link[v]==-1 || dfs(link[v])) //找增廣路
            {
                link[v]=u;
                return true;
            }
        }
    }
    return false;
}
int hungary()
{
    int res=0;
    int i,u;
    memset(link,-1,sizeof(link));
    for(u=0;u<uN;u++)
    {
        memset(used,0,sizeof(used));
        if(dfs(u))
            res++;
    }
    return res;
}  
 

以上是匈牙利算法的關鍵代碼
其實實現就是一個找增廣路徑的過程
增廣路徑 字面意思就是把路徑越增越廣
實際意思也是一樣的
DFS從左邊起始點開始搜索
1.右邊如果沒匹配就匹配(link[v]==-1)
2.如果右邊匹配過了...就從右邊點找左邊的匹配點再搜索看是否能增廣

以上兩種情況都能使匹配邊+1

這就是找二分圖最大匹配的最簡單算法了,代碼很短,時間復雜度為O(n^3),網絡流當然也能實現咯...

記住咯: 
最小點覆蓋 = 二分圖最大匹配
最小路徑覆蓋 = |P| - 二分圖最大匹配