2017年12月25日
二分图匹配的一种算法:匈牙利算法
这里不介绍算法,只提供模板代码。所有代码基于【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;
}