二分图最大匹配
匈牙利算法
思路
算法核心：找“增广路”
遍历所有左侧点，每次进行一下流程：
- 尝试去寻找一个右侧点来匹配；
- 若该右侧点还没有匹配的左侧点，则找到了，回溯。否则进入改右侧点的匹配左侧点，回到1。
代码
const int N = 505;
int n, m, tag;
vector<int> g[N];
int match[N], vis[N];
int ans;
bool dfs(int u)
{
vis[u] = tag;
for (auto &&v : g[u])
if (!match[v] || vis[match[v]] != tag && dfs(match[v]))
{
match[v] = u;
return true;
}
return false;
}
int main()
{
#ifdef aquazhao
freopen("data.in", "r", stdin);
// freopen("data.out", "w", stdout);
#endif
int x;
cin >> n >> x >> m;
int u, v;
for (int i = 1; i <= m; i++)
scanf("%d%d", &u, &v), g[u].push_back(v);
for (int i = 1; i <= n; i++)
{
++tag;
ans += dfs(i);
}
cout << ans << endl;
return 0;
}