1 条题解
-
0
#include <bits/stdc++.h> using namespace std; const int N = 410, M = 1e6 + 10; struct edge { int x, y, f, pre; }a[M]; int alen, last[N], cur[N]; void ins(int x, int y, int f) { ++alen; a[alen] = edge{ x, y, f, last[x] }; last[x] = alen; ++alen; a[alen] = edge{ y, x, 0, last[y] }; last[y] = alen; } int h[N], st, ed; bool bfs() { deque<int> Q; Q.clear(); memset(h, 0, sizeof(h)); h[st] = 1; Q.push_back(st); while (!Q.empty()) { int x = Q.front(); Q.pop_front(); for (int k = last[x]; k; k = a[k].pre) if (a[k].f) { int y = a[k].y; if (h[y] == 0) { h[y] = h[x] + 1; Q.push_back(y); } } } return h[ed] > 0; } int dinic(int x, int f) { if (x == ed) return f; int sx = 0; for (int k = cur[x]; k > 0; k = a[k].pre) if (a[k].f) { cur[x] = k; int y = a[k].y; if (h[y] == h[x] + 1) { int sy = dinic(y, min(a[k].f, f - sx)); a[k].f -= sy; a[k ^ 1].f += sy; sx = sx + sy; if (sx == f) return f; } } if (sx == 0) h[x] = 0; return sx; } int main() { int n, F, D; scanf("%d%d%d", &n, &F, &D); alen = 1; memset(last, 0, sizeof(last)); st = F + D + 2 * n + 1; ed = st + 1; for (int i = 1; i <= F; i++) ins(st, i, 1); for (int i = 1; i <= D; i++) ins(F + 2 * n + i, ed, 1); for (int i = 1; i <= n; i++) ins(F + i, F + n + i, 1); for (int i = 1; i <= n; i++) { int Fi, Di, Fx, Dx; scanf("%d%d", &Fi, &Di); for (int j = 1; j <= Fi; j++) scanf("%d", &Fx), ins(Fx, F + i, 1); for (int j = 1; j <= Di; j++) scanf("%d", &Dx), ins(F + n + i, F + 2 * n + Dx, 1); } int s = 0; while (bfs()) { memcpy(cur, last, sizeof(last)); s += dinic(st, 1 << 30); } printf("%d", s); return 0; }
- 1
信息
- ID
- 308
- 时间
- 2000ms
- 内存
- 128MiB
- 难度
- 7
- 标签
- 递交数
- 271
- 已通过
- 66
- 上传者