POJ.3291 Dining

1.Problem
http://poj.org/problem?id=3281

2.Idea
Max Flow

3.Source

 #define MAX_V 500  
 int N, F, D;  
 struct edge { int to, cap, rev; };  
 vector<edge> G[MAX_V];  
 bool used[MAX_V];  
 void add_edge(int from, int to, int cap)  
 {  
      edge e1, e2;  
      e1.to = to;  
      e1.cap = cap;  
      e1.rev = G[to].size();  
      G[from].push_back(e1);  
      e2.to = from;  
      e2.cap = 0;  
      e2.rev = G[from].size() - 1;  
      G[to].push_back(e2);  
 }  
 int dfs(int v, int t, int f)   
 {  
      if (v == t) return f;  
      used[v] = true;  
      for (int i = 0; i < G[v].size(); i++) {  
           edge &e = G[v][i];  
           if (!used[e.to] && e.cap > 0) {  
                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;  
 }

//Ford-Fulkersen  
 int max_flow(int s, int t)  
 {  
      int flow = 0;  
      for (;;) {  
           memset(used, 0, sizeof used);  
           int f = dfs(s, t, INF);  
           if (f == 0) {  
                return flow;  
           }  
           flow += f;  
      }  
 }  
 int main() {  
      int N, F, D;  
      scanf("%d %d %d", &N, &F, &D);  
      for (int i = 0; i < F; i++) {  
           add_edge(0, 1 + i, 1);  
      }  
      for (int i = 0; i < N; i++) {  
           int Fi, Di;  
           scanf("%d %d", &Fi, &Di);  
           while (Fi--) {  
                int f;  
                scanf("%d", &f);  
                add_edge(1 + (f - 1), 1 + F + i, 1);  
           }  
           add_edge(1 + F + i, 1 + F + N + i, 1);  
           while (Di--) {  
                int d;  
                scanf("%d", &d);  
                add_edge(1 + F + N + i, 1 + F + N + N + (d - 1), 1);  
           }  
      }  
      for (int i = 0; i < D; i++) {  
           add_edge(1 + F + N + N + i, 1 + F + N + N + D, 1);  
      }  
      printf("%d\n", max_flow(0, 1 + F + N + N + D));  
 }