挑战程序设计3.5第3题 Dining

 1 #include <iostream>
 2 #include <string.h>
 3 #include <algorithm>
 4 #include <vector>
 5 using namespace std;
 6 
 7 int N, F, D;
 8 bool mapf[105][105], mapd[105][105];
 9 
10 
11 struct edge { 
12     int to, cap, rev;
13     edge(int a, int b, int c) :to(a), cap(b), rev(c) {}
14 };
15 
16 vector<edge> G[405];
17 bool vis[405];
18 
19 void add_edge(int from, int to, int cap) {    //建边及反向边
20     edge a(to, cap, G[to].size());
21     G[from].push_back(a);
22     edge b(from, 0, G[from].size() - 1);
23     G[to].push_back(b);
24 }
25 
26 int dfs(int v, int t, int f) {
27     if(v == t) return f;
28     vis[v] = true;
29     for (int i = 0; i < G[v].size(); i++) {
30         edge &e = G[v][i];
31         if (!vis[e.to] && e.cap > 0) {
32             int d = dfs(e.to, t, min(f, e.cap));
33             if (d > 0) {
34                 e.cap -= d;
35                 G[e.to][e.rev].cap += d;
36                 return d;
37             }
38         }
39     }
40     return 0;
41 }
42 
43 int max_flow(int s, int t) {
44     int flow = 0;
45     for (;;) {
46         memset(vis, 0, sizeof(vis));
47         int f = dfs(s, t, 1000);
48         if (f == 0)return flow;
49         flow += f;
50     }
51     return flow;
52 }
53 
54 void solve() {
55     int t = 0, s = 2 * N + F + D + 1;    
56     for (int i = 1; i <= F; i++) {  //建起点t与食物的边
57         add_edge(t, 2 * N + i, 1);
58     }
59     for (int i = 1; i <= D; i++) {  //建饮料与终点s的边
60         add_edge(2 * N + F + i, s, 1);
61     }
62     for (int i = 1; i <= N; i++) {//建牛的边及与食物和饮料的边
63         add_edge(i, N + i, 1);
64         for (int j = 1; j <= F; j++) {
65             if (mapf[j][i])add_edge(2 * N + j, i, 1);
66         }
67         for (int j = 1; j <= D; j++) {
68             if (mapd[i][j])add_edge(N + i, 2 * N + F + j, 1);
69         }
70     }
71     cout << max_flow(t, s) << endl;
72 }
73 
74 int main()
75 {
76     cin >> N >> F >> D;
77     memset(mapf, false, sizeof(mapf));
78     memset(mapd, false, sizeof(mapd));
79     for (int i = 1; i <= N; i++) {
80         int f, d;
81         cin >> f >> d;
82         for (int j = 0; j < f; j++) {
83             int a;
84             cin >> a;
85             mapf[a][i] = true;
86         }
87         for (int j = 0; j < d; j++) {
88             int a;
89             cin >> a;
90             mapd[i][a] = true;
91         }
92     }
93     solve();
94     return 0;
95 }