洛谷P7368 [USACO05NOV] Asteroids G 题解 二分图最小点覆盖 匈牙利算法

题目链接：https://www.luogu.com.cn/problem/P7368

二分图最小点覆盖 模板题。

二分图最小点覆盖与二分图最大匹配的关系。

所以用匈牙利算法求一下二分图最大匹配即可。

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;int n, m, match[maxn], ans;
vector<int> g[maxn];
bool vis[maxn];int find(int u) {for (auto v : g[u]) {if (vis[v])continue;vis[v] = true;if (!match[v] || find(match[v])) {match[v] = u;return true;}}return false;
}int main() {cin >> n >> m;while (m--) {int u, v;cin >> u >> v;g[u].push_back(v);}for (int i = 1; i <= n; i++) {memset(vis, 0, sizeof vis);if (find(i))ans++;}cout << ans << endl;return 0;
}