题意：给定每个人所喜欢的食物和饮料种类以及每种食物和饮料的数量，一个人需要一种食物和一种饮料（数量为1即可），问最多满足多少人的需要

思路：由于食物和饮料对于人来说需要同时满足，它们是“与”的关系，所以建模时需要放在不同的层，另外如果把人放在根，食物和饮料依次放后面，则每个人会扩展出f*d个节点出来，边数有f*d条，而如果把人放中间，类似于“双向广搜”的原理，层数减半，边数大大减少。具体来说，从源点向每种食物连边，容量为其数量，如果某个人喜欢某种食物，则从食物向人连边，容量为1，为了限制人只能选择一个食物和饮料，需要人为地加n个新节点与每个人一一对应，从人向其所对应的新节点连一条容量为1的边，然后向喜欢的饮料各连一条容量为1的边，最后连回汇点，容量为饮料数量。图如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
/* ******************************************************************************** */
#include <iostream>                                                                 //
#include <cstdio>                                                                   //
#include <cmath>                                                                    //
#include <cstdlib>                                                                  //
#include <cstring>                                                                  //
#include <vector>                                                                   //
#include <ctime>                                                                    //
#include <deque>                                                                    //
#include <queue>                                                                    //
#include <algorithm>                                                                //
#include <map>                                                                      //
using namespace std;                                                                //
                                                                                    //
#define pb push_back                                                                //
#define mp make_pair                                                                //
#define X first                                                                     //
#define Y second                                                                    //
#define all(a) (a).begin(), (a).end()                                               //
#define foreach(a, i) for (typeof(a.begin()) i = a.begin(); i != a.end(); ++ i)     //
#define fill(a, x) memset(a, x, sizeof(a))                                          //
                                                                                    //
void RI(vector<int>&a,int n){a.resize(n);for(int i=0;i<n;i++)scanf("%d",&a[i]);}    //
void RI(){}void RI(int&X){scanf("%d",&X);}template<typename...R>                    //
void RI(int&f,R&...r){RI(f);RI(r...);}void RI(int*p,int*q){int d=p<q?1:-1;          //
while(p!=q){scanf("%d",p);p+=d;}}void print(){cout<<endl;}template<typename T>      //
void print(const T t){cout<<t<<endl;}template<typename F,typename...R>              //
void print(const F f,const R...r){cout<<f<<", ";print(r...);}template<typename T>   //
void print(T*p, T*q){int d=p<q?1:-1;while(p!=q){cout<<*p<<", ";p+=d;}cout<<endl;}   //
                                                                                    //
typedef pair<int, int> pii;                                                         //
typedef long long ll;                                                               //
typedef unsigned long long ull;                                                     //
                                                                                    //
template<typename T>bool umax(T&a, const T&b){return b>a?false:(a=b,true);}         //
template<typename T>bool umin(T&a, const T&b){return b<a?false:(a=b,true);}         //
template<typename T>                                                                //
void V2A(T a[],const vector<T>&b){for(int i=0;i<b.size();i++)a[i]=b[i];}            //
template<typename T>                                                                //
void A2V(vector<T>&a,const T b[]){for(int i=0;i<a.size();i++)a[i]=b[i];}            //
                                                                                    //
/* -------------------------------------------------------------------------------- */
 
 
struct Dinic {
private:
    const static int maxn = 800 + 7;
    struct Edge {
        int from, to, cap;
        Edge(int u, int v, int w): from(u), to(v), cap(w) {}
    };
    int s, t;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool vis[maxn];
    int d[maxn], cur[maxn];
 
    bool bfs() {
        memset(vis, 0, sizeof(vis));
        queue<int> Q;
        Q.push(s);
        d[s] = 0;
        vis[s] = true;
        while (!Q.empty()) {
            int x = Q.front(); Q.pop();
            for (int i = 0; i < G[x].size(); i ++) {
                Edge &e = edges[G[x][i]];
                if (!vis[e.to] && e.cap) {
                    vis[e.to] = true;
                    d[e.to] = d[x] + 1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    int dfs(int x, int a) {
        if (x == t || a == 0) return a;
        int flow = 0, f;
        for (int &i = cur[x]; i < G[x].size(); i ++) {
            Edge &e = edges[G[x][i]];
            if (d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap))) > 0) {
                e.cap -= f;
                edges[G[x][i] ^ 1].cap += f;
                flow += f;
                a -= f;
                if (a == 0) break;
            }
        }
        return flow;
    }
 
public:
    void clear() {
        for (int i = 0; i < maxn; i ++) G[i].clear();
        edges.clear();
        memset(d, 0, sizeof(d));
    }
    void add(int from, int to, int cap) {
        edges.push_back(Edge(from, to, cap));
        edges.push_back(Edge(to, from, 0));
        int m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }
 
    int solve(int s, int t) {
        this->s = s; this->t = t;
        int flow = 0;
        while (bfs()) {
            memset(cur, 0, sizeof(cur));
            flow += dfs(s, 1e9);
        }
        return flow;
    }
 
};
Dinic solver;
const int maxn = 207;
int cf[maxn], cd[maxn];
bool likef[maxn][maxn], liked[maxn][maxn];
 
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE
    int n, f, d;
    while (cin >> n >> f >> d) {
        RI(cf + 1, cf + 1 + f);
        RI(cd + 1, cd + 1 + d);
        for (int i = 1; i <= n; i ++) {
            char s[234];
            scanf("%s", s);
            for (int j = 0; j < f; j ++) {
                likef[i][j + 1] = s[j] == 'Y';
            }
        }
        for (int i = 1; i <= n; i ++) {
            char s[234];
            scanf("%s", s);
            for (int j = 0; j < d; j ++) {
                liked[i][j + 1] = s[j] == 'Y';
            }
        }
        solver.clear();
        for (int i = 1; i <= f; i ++) {
            solver.add(0, i, cf[i]);
        }
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= f; j ++) {
                if (likef[i][j]) solver.add(j, f + i, 1);
            }
        }
        for (int i = 1; i <= n; i ++) {
            solver.add(f + i, f + n + i, 1);
        }
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= d; j ++) {
                if (liked[i][j]) solver.add(f + n + i, f + n + n + j, 1);
            }
        }
        for (int i = 1; i <= d; i ++) {
            solver.add(f + n + n + i, f + n + n + d + 1, cd[i]);
        }
        cout << solver.solve(0, f + n + n + d + 1) << endl;
    }
    return 0;                                                                       //
}                                                                                   //
                                                                                    //
                                                                                    //
                                                                                    //
/* ******************************************************************************** */

最新文章

  1. 那些年构建SSH所遇到的坑
  2. MVC4脚本压缩 BundleTable bundles 404错误
  3. ppDelegate的相关介绍
  4. 常用 windows运行命令
  5. C# 小规模查找集合性能测试
  6. PHPer 为什么会被 Javaer 鄙视？
  7. ehcharts中国地图四级级下钻
  8. myEclipse 8.5下SVN环境的搭建
  9. [每天一个Linux小技巧]　强制让内核按单核模式启动
  10. 002-如何理解Java的平台独立性
  11. springboot整合JPA(简单整理，待续---）
  12. Python爬虫之诗歌接龙
  13. sql新语句
  14. Angular injector注入器
  15. MVC ---- EF的延迟加载
  16. Oracle安装盘空间不足，对.DBF文件进行迁移
  17. 6.2 - BBS + BLOG系统
  18. Java概述、环境变量、注释、关键字、标识符、常量
  19. 怎样彻底清除UniAccess Agent
  20. html格式

热门文章

  1. 原创hadoop2.6集群环境搭建
  2. Gatling脚本编写技巧篇（二）
  3. 极验反爬虫防护分析之slide验证方式下图片的处理及滑动轨迹的生成思路
  4. pyinstaller打包
  5. [转]ThinkCMF框架任意内容包含漏洞分析复现
  6. C++头文件问题
  7. python 获取的json字符串取值
  8. 树莓派3b在rt-thread上移植LittlevGL
  9. Python自然语言处理实战核心技术与算法，Python自然语言处理，PyTorch深度学习实战【下载】
  10. Java 解析 xml 常见的4中方式：DOM SAX JDOM DOM4J