匈牙利算法
#算法
匈牙利算法是解决二分图中最大边匹配（即最小点覆盖）的一种高效算法，时间复杂度为O(VE) （点边乘积）
- 最大边匹配： 在图中选取尽可能多的边，使得这些边之间没有公共顶点
- 最小点覆盖： 覆盖所有边所需要最少的点（边上两点之一被选中该边即视为被覆盖）
- 匈牙利算法的核心： dfs不断寻找增广路径判断是否可以匹配
C++算法：
//code by homgzha
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, k;
const int N = 505;
int st[N];
int match[N];
int g[N][N];
bool dfs(int u) {
for (int i = 0;i < N;i++) {
if (g[u][i] && !st[i]) {
st[i] = 1;
if (!match[i] || dfs(match[i])) {
match[i] = u;return true;
}
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
while (cin >> k >> m >> n) {
memset(g, 0, sizeof g);
memset(match, 0, sizeof match);
int x, y;
while (k--) {
cin >> x >> y;
g[x][y] = 1;
}
int ans = 0;
for (int i = 1;i <= m;i++) {
memset(st, 0, sizeof st);
if (dfs(i))ans++;
}
cout << ans << endl;
}
return 0;
}