呜呜,思路与第一篇题解一模一样,就连代码都改到几乎一样了,还是30分
#include<bits/stdc++.h>
#define il inline
#define re register
#define ll long long
#define ull unsigned ll
#define uint unsigned int
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define IT iterator
#define pr pair
#define pq priority_queue
#define mpr make_pair
#define int ll
const int N = 1e5 + 5, inf = 0x3f3f3f3f;
const double pi = acos(-1);
il int R () {
re int s = 0, f = 1; re char ch = getchar();
while (!isdigit(ch)) f = (ch == '-') ? -1 : 1, ch = getchar();
while (isdigit(ch)) s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
return s * f;
}
int n, f, d, head[N], nxt[N], to[N], edge[N], tot = -1, S, T, cur[N], dis[N];
il void add_edge (int u, int v, int w) {
nxt[++tot] = head[u], to[tot] = v, head[u] = tot, edge[tot] = w;
return ;
}
std :: queue <int> q;
il int bfs () {
std :: memset(dis, -1, sizeof(dis));
dis[S] = 0, q.push(S);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = head[u]; i != -1; i = nxt[i]) {
int v = to[i];
if (dis[v] == -1 && edge[i]) q.push(v), dis[v] = dis[u] + 1;
}
}
return (dis[T] != -1);
}
il int dfs (int u, int flow) {
if (u == T) return flow;
int now = flow;
for (int i = cur[u]; i != -1; i = nxt[i]) {
cur[u] = i;
int v = to[i];
if (dis[v] == dis[u] + 1 && edge[i] > 0) {
int minn = dfs(v, std :: min(now, edge[i]));
edge[i] -= minn, edge[i ^ 1] += minn;
now -= minn;
}
if (now <= 0) break;
}
return flow - now;
}
il int dinic () {
int ret = 0;
while (bfs()) {
for (int i = 1; i <= T; i++) cur[i] = head[i];
ret += dfs(S, inf);
}
return ret;
}
signed main () {
n = R(), f = R(), d = R();
S = 1, T = n + f + d + n + f + d;
std :: memset(head, -1, sizeof(head));
for (int i = 1; i <= f; i++) {
add_edge(S, i + 1, 1);
add_edge(i + 1, S, 0);
}
for (int i = 1; i <= d; i++) {
add_edge(1 + f + n + i, T, 1);
add_edge(T, 1 + f + n + i, 0);
}
for (int i = 1; i <= n; i++) {
add_edge(1 + f + i, 2 + f + n + d + i, 1);
add_edge(2 + f + n + d + i, 1 + f + i, 0);
}
for (int i = 1; i <= n; i++) {
int k1 = R(), k2 = R();
for (int j = 1; j <= k1; j++) {
int u = R();
add_edge(1 + u, 1 + f + i, 1);
add_edge(i + f + i, 1 + u, 0);
}
for (int j = 1; j <= k2; j++) {
int v = R();
add_edge(2 + f + n + d + i, 1 + v + f + n, 1);
add_edge(1 + v + f + n, 2 + f + n + d + i, 0);
}
}
return !printf("%lld", dinic());
}