匈牙利演算法

用於二分圖匹配問題
二分圖:有兩個集合,集合內元素互不相連接,兩個集合間元素和元素間可互相連接,如下圖

最大匹配數

定義:找到最多合法匹配元素使的總數最多

原則:

  1. 如果此元素未被配對 => 直接與此元素配對
  2. 如果此元素已配對 => 找看看此元素是否可與其他元素匹配,如果可以,此元素匹配改為當前元素,如果不行,繼續試下一個





















//  p[i]代表與此元素匹配的元素,初始化為0
bool match(int now){
    for(int i=1;i<=N;i++){
        if(Map[now][i]==1){  //如果此2元素有連接才能走
            if(!p[i]){  
                //如果此元素還未被配對
                p[i]=now;
                //直接與此元素配對
                return true;
            }else{  //否則此元素已被配對
                if(match(p[i])){
                    //檢查此已配對元素是否可與其他元素配對
                    p[i]=now;
                    //如果可以就把此元素改成當前元素now
                    return true;
                }
            }
        }
    }
    return false;
}

兩者可合併簡化:












bool match(int now){
    for(int i=1;i<=N;i++){
        if(Map[now][i]){
            if(!p[i] || match(p[i])){
                p[i]=now;
                return true
            }
        }
    }
    return false;
}

但由於遞迴的關係可能會回到起始點,就會從起始點再一次遞迴,最後會TLE,所以要判斷此點是否visited















//p[i]代表右邊的i和左邊的p[i]節點匹配
//Map[x][y]代表左邊的x節點和右邊的y節點有連通
bool match(int now){
    for(int i=1;i<=N;i++){
        if(Map[now][i] && !visit[i]){  //判斷該點有沒有被訪問過
            visit[i]=true;  //代表該點已走過,不用在判斷能否匹配
            if(!p[i] || match(p[i])){
                p[i]=now;
                return true
            }
        }
    }
    return false;
}

圖的版本:













bool match(int now){
    for(auto i:Map[now]){
        if(!vis[i]){
            vis[i]=true;
            if(p[i]==0 || match(p[i])){
                p[i]=now;
                return true;
            }
        }
    }
    return false;
}

最小點覆蓋數

定義:找到一些最少的點,使的二分圖所有的邊都至少有一個端點在這些點之中,也就是說,刪掉包含這些點的邊,可以刪掉二分圖所有的邊

Konig定理:二分圖中最小點覆蓋數等於最大匹配數

題目:zerojudge C455














































#include <bits/stdc++.h>
using namespace std;

#define MAXN 100005
vector<int> graph[MAXN];
int match[MAXN];
bitset<MAXN> vis;

bool Try(int now) {
    for (auto i : graph[now]) {
        if (!vis[i]) {
            vis[i] = true;
            if (!match[i] || Try(match[i])) {
                match[i] = now;
                return true;
            }
        }
    }
    return false;
}

int main() {
    cin.sync_with_stdio(0), cin.tie(0);
    int t, n, m;
    cin >> t;
    while (t--) {
        int k, x, y;
        cin >> n >> m >> k;

        for (int i = 1; i <= n; i++) graph[i].clear();
        for (int i = 1; i <= m; i++) match[i] = 0;

        for (int i = 0; i < k; i++) {
            cin >> x >> y;
            graph[x].push_back(y);
        }
        int matchCnt = 0;
        for (int i = 1; i <= n; i++) {
            vis.reset();
            if (Try(i)) matchCnt++;
        }
        cout << matchCnt << '\n';
    }
    return 0;
}

Kuhn Munkres algorithm

上述匈牙利演算法是用來求最大匹配數，KM演算法則是求最大權重完美匹配數,也就是說,每個元素都要有匹配,求最大權重為何

總共會需要以下陣列








int love[MAXN][MAXN];  //兩點元素之間的權重(好感度)
int ex_girl[MAXN];  //girl的頂標
int ex_boy[MAXN];  //boy的頂標
int vis_girl[MAXN];  //有無拜訪過這個girl
int vis_boy[MAXN];  //有無拜訪過這個boy
int match[MAXN];  //這個boy配對到的girl
int N,minz;  //minz表最小機會成本
  1. 初始化
    每個男生的頂標都設為0
    每個女生的頂標設為當前女生對應所有男生中,好感度最大的權重
    每個男生的match都設為-1,表還沒配對











void init(){
    for(int i=0;i<N;i++){
        ex_boy[i]=0;
        match[i]=-1;

        ex_girl[i]=love[i][0];
        for(int j=1;j<N;j++){
            ex_girl[i]=max(ex_girl[i],love[i][j]);
        }
    }
}
  1. 每次執行的dfs
    跟匈牙利演算法差不多,差別在於兩點
    (1)求最小機會成本
    機會成本:在當前參與配對的girl對應未參與配對的boy中,頂標和-權重(好感
    度)
    (2)對於頂標和=權重的邊才要更新


















bool dfs(int girl){
    vis_girl[girl]=true;

    for(int boy=0;boy<N;boy++){
        if(!vis_boy[boy] && ex_girl[girl]+ex_boy[boy]==love[girl][boy]){ 
            //頂標和=權重才能更新
            vis_boy[boy]=true;
            if(match[boy]==-1 || dfs(match[boy])){
                match[boy]=girl;
                return true;
            }
        }else if(!vis_boy[boy]){  
            //對於參與配對的girl與未參與配對的boy才要求最小機會成本
            minz=min(minz,ex_girl[girl]+ex_boy[boy]-love[girl][boy]);
        }
    }
    return false;
}
  1. 找不到配對就updata
    對於剛剛參與配對的所有人都要更新頂標
    其中,女生要減掉最小機會成本
    男生要加上最小機會成本






void update(){
    for(int i=0;i<N;i++){
        if(vis_girl[i]) ex_girl[i]-=minz;
        if(vis_boy[i]) ex_boy[i]+=minz;
    }
}

完整Code
1042 . E.老問題


























































































#include <bits/stdc++.h>
#define MAXN 105
using namespace std;

int love[MAXN][MAXN];
int ex_girl[MAXN];
int ex_boy[MAXN];
int vis_girl[MAXN];
int vis_boy[MAXN];
int match[MAXN];
int N,minz;

bool dfs(int girl){
    vis_girl[girl]=true;

    for(int boy=0;boy<N;boy++){
        if(!vis_boy[boy] && ex_girl[girl]+ex_boy[boy]==love[girl][boy]){
            vis_boy[boy]=true;
            if(match[boy]==-1 || dfs(match[boy])){
                match[boy]=girl;
                return true;
            }
        }else if(!vis_boy[boy]){
            minz=min(minz,ex_girl[girl]+ex_boy[boy]-love[girl][boy]);
        }
    }
    return false;
}

void init(){
    for(int i=0;i<N;i++){
        ex_boy[i]=0;
        match[i]=-1;

        ex_girl[i]=love[i][0];
        for(int j=1;j<N;j++){
            ex_girl[i]=max(ex_girl[i],love[i][j]);
        }
    }
}

void update(){
    for(int i=0;i<N;i++){
        if(vis_girl[i]) ex_girl[i]-=minz;
        if(vis_boy[i]) ex_boy[i]+=minz;
    }
}

int KM(){
    init();

    //KM
    for(int j=0;j<N;j++){  //為每個girl都配對一個boy

        while(1){
            //init
            memset(vis_girl,0,sizeof(ex_girl));
            memset(vis_boy,0,sizeof(ex_boy));
            minz=1e9;

            if(!dfs(j)) update();  //如果配對失敗,則更新頂標
            else break;  //直到配對成功
        }
    }
    
    //get ans
    int ans=0;
    for(int i=0;i<N;i++){
        ans+=love[match[i]][i];  
        //把match[i]這個女生對應到的男生i的好感度加到ans
    }
    return ans;
}

int main(){
    cin.sync_with_stdio(0),cin.tie(0);

    while(cin >> N && N){
        
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                cin >> love[i][j];
                love[i][j]=max(love[i][j],0);
            }
        }
        cout << KM() << '\n';
    }
    return 0;
}
Select a repo