[kuangbin]带你飞之'网络流'专题

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<queue>
  4 #define INF 0x3f3f3f3f
  5 using namespace std;
  6 
  7 inline int read() {
  8     char c=getchar();int x=0,f=1;
  9     while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
 10     while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}
 11     return x*f;
 12 }
 13 
 14 const int MAXN = 30000+5;
 15 const int MAXE = 20400+5;
 16 
 17 int num;
 18 int head[MAXN];
 19 struct node {
 20     int v, flow;
 21     int next;
 22 } edge[MAXE];
 23 
 24 inline void add(int x, int y, int w) {
 25     edge[num].v = y;
 26     edge[num].flow = w;
 27     edge[num].next = head[x];
 28     head[x] = num++;
 29 }
 30 
 31 int n, cows, food, drink;
 32 int cur[MAXN], dis[MAXN];
 33 
 34 bool bfs() {
 35     for(int i = 1; i <= n; ++i) dis[i] = 0;
 36     dis[1] = 1;
 37     queue<int> q;
 38     q.push(1);
 39     while(!q.empty()) {
 40         int u = q.front();
 41         q.pop();
 42         for(int i = head[u]; i != -1; i = edge[i].next) {
 43             int v = edge[i].v;
 44             if(!dis[v] && edge[i].flow) {
 45                 dis[v] = dis[u] + 1;
 46                 q.push(v);
 47             }
 48         }
 49     }
 50     return dis[n] != 0;
 51 }
 52 
 53 int dfs(int u, int f) {
 54     if(u == n || (!f)) return f;
 55     int flow = 0;
 56     for(int& i = cur[u]; i != -1; i = edge[i].next) {
 57         int v = edge[i].v;
 58         if(dis[v] == dis[u] + 1) {
 59             int di = dfs(v, min(f, edge[i].flow));
 60             if(di > 0) {
 61                 flow += di;
 62                 f -= di;
 63                 edge[i].flow -= di;
 64                 edge[i^1].flow += di;
 65                 if(!f) break;
 66             }
 67         }
 68     }
 69     if(!flow) dis[u] = -1;
 70     return flow;
 71 }
 72 
 73 int Dinic() {
 74     int ans = 0;
 75     while(bfs()) {
 76         for(int i = 1; i <= n; ++i) cur[i] = head[i];
 77         ans += dfs(1, INF);
 78     }
 79     return ans;
 80 }
 81 
 82 
 83 int main() {
 84     cows = read(); food = read(); drink = read();
 85     n = cows*2 + food + drink + 2;
 86     num = 0;
 87     for(int i = 1; i <= n; ++i) head[i] = -1;
 88     for(int i = 2; i <= 1+food; ++i) {
 89         add(1, i, 1);
 90         add(i, 1, 0);
 91     }
 92     for(int i = 2+food+cows*2; i <= 1+food+cows*2+drink; ++i) {
 93         add(i, n, 1);
 94         add(n, i, 0);
 95     }
 96     int fn, dn, x;
 97     for(int i = 2+food; i <= 1+food+cows; ++i) {
 98         fn = read(); dn = read();
 99         for(int j = 0; j != fn; ++j) {
100             x = read();
101             add(1+x, i, 1);
102             add(i, 1+x, 0);
103         }
104         for(int j = 0; j != dn; ++j) {
105             x = read();
106             add(i+cows, 1+food+cows*2+x, 1);
107             add(1+food+cows*2+x, i+cows, 0);
108         }
109         add(i, i+cows, 1);
110         add(i+cows, i, 0);
111     }
112     printf("%d\n", Dinic());
113     return 0;
114 }