二分图匹配的一种算法:匈牙利算法

二分图匹配的一种算法:匈牙利算法

这里不介绍算法,只提供模板代码。所有代码基于【P3386】【模板】二分图匹配 – 洛谷一题。

匈牙利算法

// Code by KSkun, 2017/12
#include <cstdio>
#include <cstring>
#include <vector>

struct io {
    char buf[1 << 26], *s;

    io() {
        fread(s = buf, 1, 1 << 26, stdin);
    }

    inline int read() {
        register int res = 0;
        while(*s < '0' || *s > '9') s++;
        while(*s >= '0' && *s <= '9') res = res * 10 + *s++ - '0';
        return res;
    }
};

io ip;

#define read ip.read 

std::vector<int> vec[2005]; 

int n, m, e;
bool vis[2005];
int match[2005];

inline bool dfs(int u) {
    for(int i = 0; i < vec[u].size(); i++) {
        int v = vec[u][i];
        if(!vis[v]) {
            vis[v] = true;
            if(match[v] == -1 || dfs(match[v])) {
                match[v] = u;
                match[u] = v;
                return true;
            }
        }
    }
    return false;
} 

inline int hungarian() {
    int ans = 0;
    memset(match, -1, sizeof match);
    for(int i = 1; i <= n; i++) {
        if(match[i] == -1) {
            memset(vis, 0, sizeof vis);
            if(dfs(i)) ans++;
        }
    }
    return ans;
}

int ut, vt;

int main() {
    n = read();
    m = read();
    e = read();
    for(int i = 0; i < e; i++) {
        ut = read();
        vt = read();
        if(ut > n || vt > m) continue;
        vec[ut].push_back(n + vt);
        vec[n + vt].push_back(ut);
    }
    printf("%d", hungarian());
    return 0;
}


发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据