溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

C語(yǔ)言[二分圖最大匹配] 匈牙利算法的代碼

發(fā)布時(shí)間：2020-07-31 01:22:13 來(lái)源：網(wǎng)絡(luò) 閱讀：1196 作者：oldpman 欄目：編程語(yǔ)言

將寫代碼過(guò)程中重要的一些代碼片段珍藏起來(lái)，如下的代碼是關(guān)于C語(yǔ)言[二分圖最大匹配] 匈牙利算法的代碼，應(yīng)該是對(duì)各位有一些好處。

const int INF = 0x3f3f3f3f; 
const int MAXN=510;
{
    int v;
    {
        {
            used[v]=true;
            {
                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;
}

以上是匈牙利算法的關(guān)鍵代碼其實(shí)實(shí)現(xiàn)就是一個(gè)找增廣路徑的過(guò)程增廣路徑字面意思就是把路徑越增越廣實(shí)際意思也是一樣的DFS從左邊起始點(diǎn)開(kāi)始搜索1.右邊如果沒(méi)匹配就匹配(link[v]==-1)2.如果右邊匹配過(guò)了...就從右邊點(diǎn)找左邊的匹配點(diǎn)再搜索看是否能增廣以上兩種情況都能使匹配邊+1這就是找二分圖最大匹配的最簡(jiǎn)單算法了,代碼很短,時(shí)間復(fù)雜度為O(n^3),網(wǎng)絡(luò)流當(dāng)然也能實(shí)現(xiàn)咯...記住咯:最小點(diǎn)覆蓋=二分圖最大匹配最小路徑覆蓋=|P|-二分圖最大匹配PS:網(wǎng)絡(luò)流還沒(méi)看...悲劇...滾去看DINIC了...

向AI問(wèn)一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手