挑战程序设计P235
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; const int maxn = 1000; const int INF = 0x3f3f3f3f; struct Edge { int to, cap, rev; Edge(int x, int y, int z) : to(x), cap(y), rev(z) {} }; vector<Edge> G[maxn]; int level[maxn], iter[maxn]; void addedge(int u, int v, int cap) { G[u].push_back(Edge(v, cap, G[v].size())); G[v].push_back(Edge(u, 0, G[u].size()-1)); } void bfs(int s) { memset(level, -1, sizeof(level)); queue<int> q; level[s] = 0; q.push(s); while (!q.empty()) { int v = q.front(); q.pop(); for (int i = 0; i < G[v].size(); i++) { Edge &e = G[v][i]; if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; q.push(e.to); } } } } int dfs(int v, int t, int f) { if (v == t) return f; for (int &i = iter[v]; i < G[v].size(); i++) { Edge &e = G[v][i]; if (e.cap > 0 && level[v] < level[e.to]) { int d = dfs(e.to, t, min(f, e.cap)); if (d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } int max_flow(int s, int t) { int flow = 0; while (true) { bfs(s); if (level[t] < 0) return flow; memset(iter, 0, sizeof(iter)); int f; while (f = dfs(s, t, INF) > 0) flow += f; } } int N, F, D; int main() { while (~scanf("%d %d %d", &N, &F, &D)) { int f, d, x; for (int i = 0; i < maxn; i++) G[i].clear(); for (int i = 1; i <= F; i++) addedge(0, i, 1); for (int i = 1; i <= D; i++) addedge(F+2*N+i, F+2*N+D+1, 1); for (int i = 1; i <= N; i++) addedge(F+i, F+i+N, 1); for (int i = 1; i <= N; i++) { scanf("%d %d", &f, &d); while (f--) { scanf("%d", &x); addedge(x, F+i, 1); } while (d--) { scanf("%d", &x); addedge(F+i+N, F+2*N+x, 1); } } printf("%d\n", max_flow(0, F+2*N+D+1)); } return 0; }