题目大意:$N$个人$M$件物品,每个人喜欢若干件物品,每个人收到不少于两件自己喜欢的物品会变得开心,问最多能让几个人开心。
比较套路的拆点,考虑将每个人拆成两个点,互相连边,同时都与这个人喜欢的物品连边,这样如果一个人被分到了自己喜欢的物品,会提供两对匹配,如果没有分到物品,自己的两个点会互相匹配,提供一对匹配,显然一个人能提供匹配的对数要么是1要么是2,从而开心的人会比不开心的人多出一对匹配,用最大匹配减去总人数即是答案。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1220, M = 800000;
int e[M], ne[M], h[N], p[N], idx;
int col[N], vis[N], match[N], pre[N];
int q[N], hh, tt;
bool st[N];
int ts;
int n, m;
void insert(int u, int v) {
e[idx] = v, ne[idx] = h[u], h[u] = idx++;
e[idx] = u, ne[idx] = h[v], h[v] = idx++;
}
int find(int x) {
return x == p[x] ? x : p[x] = find(p[x]);
}
int lca(int x, int y) {
++ts;
x = find(x), y = find(y);
while (vis[x] != ts) {
vis[x] = ts;
x = find(pre[match[x]]);
if (y) swap(x, y);
}
return x;
}
void blossom(int x, int y, int w) {
while (find(x) != w) {
pre[x] = y, y = match[x];
if (col[y] == 2) col[y] = 1, q[++tt] = y;
if (find(x) == x) p[x] = w;
if (find(y) == y) p[y] = w;
x = pre[y];
}
}
bool augment(int S) {
for (int i = 1; i <= 2 * n + m; i++) {
p[i] = i;
col[i] = pre[i] = 0;
}
tt = -1, hh = 0;
q[++tt] = S, col[S] = 1;
while (hh <= tt) {
int x = q[hh++];
for (int i = h[x]; ~i; i = ne[i]) {
int y = e[i];
if (find(x) == find(y) || col[y] == 2) continue;
if (!col[y]) {
col[y] = 2, pre[y] = x;
if (!match[y]) {
do {
int z = pre[y];
int p = match[z];
match[y] = z;
match[z] = y;
y = p;
} while (y);
return true;
}
col[match[y]] = 1;
q[++tt] = match[y];
}
else {
int w = lca(x, y);
blossom(x, y, w);
blossom(y, x, w);
}
}
}
return false;
}
void solve() {
memset(h, -1, sizeof h), idx = 0;
memset(match, 0, sizeof match);
memset(vis, false, sizeof vis);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
insert(i, i + n);
int k;
cin >> k;
while (k--) {
int x;
cin >> x;
insert(x + 2 * n, i);
insert(x + 2 * n, i + n);
}
}
int res = 0;
for (int i = 1; i <= 2 * n + m; i++)
if (!match[i])
res += augment(i);
cout << res - n << '\n';
}
int main() {
int T;
cin >> T;
while (T--) solve();
return 0;
}