二分图匹配

二分图匹配

#include <cstdio>
#include <cstring>
#include <vector>using namespace std;const int maxn = 2000 + 5; // 单侧顶点的最大数目// 二分图最大基数匹配
struct BPM {int n, m;               // 左右顶点个数vector<int> G[maxn];    // 邻接表int left[maxn];         // left[i]为右边第i个点的匹配点编号，-1表示不存在bool T[maxn];           // T[i]为右边第i个点是否已标记int right[maxn];        // 求最小覆盖用bool S[maxn];           // 求最小覆盖用void init(int n, int m) {this->n = n;this->m = m;for (int i = 0; i < n; i++) G[i].clear();}void AddEdge(int u, int v) {G[u].push_back(v);}bool match(int u) {S[u] = true;for (int i = 0; i < G[u].size(); i++) {int v = G[u][i];if (!T[v]) {T[v] = true;if (left[v] == -1 || match(left[v])) {left[v] = u;right[u] = v;return true;}}}return false;}// 求最大匹配int solve() {memset(left, -1, sizeof(left));memset(right, -1, sizeof(right));int ans = 0;for (int u = 0; u < n; u++) { // 从左边结点u开始增广memset(S, 0, sizeof(S));memset(T, 0, sizeof(T));if (match(u)) ans++;}return ans;}// 求最小覆盖。X和Y为最小覆盖中的点集int mincover(vector<int> &X, vector<int> &Y) {int ans = solve();memset(S, 0, sizeof(S));memset(T, 0, sizeof(T));for (int u = 0; u < n; u++)if (right[u] == -1) match(u); // 从所有X未盖点出发增广for (int u = 0; u < n; u++)if (!S[u]) X.push_back(u); // X中的未标记点for (int v = 0; v < m; v++)if (T[v]) Y.push_back(v);  // Y中的已标记点return ans;}
};BPM solver;int n, m;int main() {while (scanf("%d%d", &n, &m) == 2) {solver.init(n, m);int s;for (int i = 1; i <= n; i++) {scanf("%d", &s);while (s--) {int v;scanf("%d", &v);solver.AddEdge(i - 1, v - 1);}}int ans = solver.solve();printf("%d\n", ans);}return 0;
}