http://acm.hdu.edu.cn/showproblem.php?pid=4292
Problem Description
You, a part-time dining service worker in your college’s dining hall, are now confused with a new problem: serve as many people as possible.
The issue comes up as people in your college are more and more difficult to serve with meal: They eat only some certain kinds of food and drink, and with requirement unsatisfied, go away directly.
You have prepared F (1 <= F <= 200) kinds of food and D (1 <= D <= 200) kinds of drink. Each kind of food or drink has certain amount, that is, how many people could this food or drink serve. Besides, You know there’re N (1 <= N <= 200) people and you too can tell people’s personal preference for food and drink.
Back to your goal: to serve as many people as possible. So you must decide a plan where some people are served while requirements of the rest of them are unmet. You should notice that, when one’s requirement is unmet, he/she would just go away, refusing any service.
Input
There are several test cases.
For each test case, the first line contains three numbers: N,F,D, denoting the number of people, food, and drink.
The second line contains F integers, the ith number of which denotes amount of representative food.
The third line contains D integers, the ith number of which denotes amount of representative drink.
Following is N line, each consisting of a string of length F. �e jth character in the ith one of these lines denotes whether people i would accept food j. “Y” for yes and “N” for no.
Following is N line, each consisting of a string of length D. �e jth character in the ith one of these lines denotes whether people i would accept drink j. “Y” for yes and “N” for no.
Please process until EOF (End Of File).
Output
For each test case, please print a single line with one integer, the maximum number of people to be satisfied.
Sample Input
4 3 3 1 1 1 1 1 1 YYN NYY YNY YNY YNY YYN YYN NNY
Sample Output
3
题意分析：
对于每个人有喜欢的饮料和食物，但是每种饮料和食物都是有限的 ，求最多可以满足多少人的需求。
解题思路：
把人拆点， 建立超级源和超级汇， 超级源连食物， 超级汇连饮料，权值为饮料和食物的数量，人和自己建边，权值为1，保证每个人只计算1次，如果一个人喜欢的饮料和食物剩余很多，就会把这个人重复计算， 把每个人与自己喜欢的饮料和食物相连，权值为1， 求最大流。
刚开始我只是用领接表来存边的，结果超时了最后改成链式前向星才过。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
#define N 1020
using namespace std;
int n, D, F, cnt, dis[N], pre[N], iter[N], head[N], inf=99999999;
char str[N];
struct data {
int v;
int w;
int next;
}edge[N*N];
void add_edge(int u, int v, int w)
{
edge[cnt].v=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
}
void bfs(int s)
{
for(int i=0; i<=F+n+n+D+1; i++)
dis[i]=-1;
queue<int>q;
q.push(s);
dis[s] = 0;
while (!q.empty())
{
int u = q.front();
q.pop();
for (int i = head[u]; i != -1; i=edge[i].next)
{
data G = edge[i];
if (G.w > 0 && dis[G.v] < 0)
{
dis[G.v] = dis[u] + 1;
q.push(G.v);
}
}
}
}
int dfs(int s, int t, int f)
{
if (s == t)
return f;
for (int &i = iter[s]; i != -1; i = edge[i].next)
{
data &G = edge[i];
if (G.w > 0 && dis[s] == dis[G.v] - 1)
{
int d = dfs(G.v, t, min(G.w, f));
if (d > 0)
{
edge[i].w-=d;
edge[i^1].w+=d;
return d;
}
}
}
return 0;
}
int Dinic(int s, int t)
{
int ans = 0;
while (1)
{
bfs(s);
if (dis[t] < 0)
return ans;
for(int i=0; i<=F+n+n+D+1; i++)
iter[i]=head[i];
int d;
while ((d = dfs(s, t, inf)) > 0)
ans += d;
}
}
int main()
{
int i, j, w, len;
while (scanf("%d%d%d", &n, &F, &D) != EOF)
{
cnt=0;
memset(head, -1, sizeof(head));
for (i = 1; i <= F; i++)
{
scanf("%d", &w);
add_edge(0, i, w);
add_edge(i, 0, 0);
}
for (i = 1; i <= n; i++)
{
add_edge(F+i, F+n+i, 1);
add_edge(F+n+i, F+i, 1);
}
for (i = 1; i <= D; i++)
{
scanf("%d", &w);
add_edge(F + n + n + i, F + n + n + D + 1, w);
add_edge(F + n + n + D + 1, F + n + n + i, 0);
}
for (i = 1; i <= n; i++)
{
scanf("%s", str+1);
len = strlen(str+1);
for (j = 1; j <= len; j++)
if (str[j] == 'Y')
{
add_edge(j, F+i, 1);
add_edge(F+i, j, 0);
}
}
for(i = 1; i <= n; i++)
{
scanf("%s", str + 1);
len = strlen(str + 1);
for (j = 1; j <= len; j++)
if (str[j] == 'Y')
{
add_edge(F+n+i, F+n+n+j, 1);
add_edge(F+n+n+j, F+n+i, 0);
}
}
printf("%d
", Dinic(0, F + n + n + D + 1));
}
return 0;
}