无知 无求

0%

hdu4292 Food

发表于 分类于 ，

F种食物 D种饮料 每个人只需要一份食物和一份饮料 但每个人都有自己的喜好 问你当前的储备最多能满足多少人的需求

一开始读错题意了…不是需要给每个人提供所有喜欢的食物或者饮料 只要某一种提供一份就够了 这就变成很基础的网络流了…

源点连食物 容量就是食物容量 饮料连汇点 容量是饮料容量 食物连人如果这个人喜欢 人连饮料一样是如果喜欢 这些容量都是1 最大流即可

我这里把人习惯性的拆开来了…实际上不拆似乎也可以?对不起想错了 为了限制每个人只花费一份必须拆

ac代码

++
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
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
const int MAXV = 2005;
const int INF = 1<<30;
struct Edge{ int to, cap, rev; };
std::vector<Edge> G[MAXV];
int level[MAXV];
int iter[MAXV]; //当前弧，之前的已经没有用了

void addedge(int from, int to, int cap) {
    G[from].push_back(Edge{to, cap, G[to].size()});
    G[to].push_back(Edge{from, 0, G[from].size()-1});
}

void bfs(int s) {
    memset(level, -1, sizeof level);
    std::queue<int> que;
    level[s] = 0;
    que.push(s);
    while (!que.empty()) {
        int v = que.front(); que.pop();
        for (int i = 0; i < G[v].size(); ++i) {
            Edge &e = G[v][i];
            if (e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[v] + 1;
                que.push(e.to);
            }
        }
    }
}

int dfs(int v, int t, int f) {
    if (v == t) return f;
    for (int &i = iter[v]; i < G[v].size(); ++i) { // 注意i是引用 实现当前弧优化
        Edge &e = G[v][i];
        if (e.cap > 0 && level[v] < level[e.to]) {
            int d = dfs(e.to, t, std::min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int maxflow(int s, int t) {
    int flow = 0;
    for (; ;) {
        bfs(s);
        if (level[t] < 0) return flow;
        memset(iter, 0, sizeof iter);
        int f;
        while ((f = dfs(s, t, INF)) > 0) {
            flow += f;
        }
    }
    return flow;
}
int main()
{
    int N,F,D;
    while(~scanf("%d%d%d",&N,&F,&D))
    {
        for(int i=0;i<(N*2+F+D+2);++i)
        {
            G[i].clear();
        }
        int start=N*2+F+D,end=start+1;
        for(int i=0;i<F;++i)
        {
            int tmp;
            scanf("%d",&tmp);
            addedge(start,N*2+i,tmp);
        }
        for(int i=0;i<D;++i)
        {
            int tmp;
            scanf("%d",&tmp);
            addedge(N*2+F+i,end,tmp);
        }
        char sta[220];
        for(int i=0;i<N;++i)
        {
            scanf("%s",sta);
            for(int j=0;j<F;++j)
            {
                if(sta[j]=='Y')
                {
                    addedge(N*2+j,i*2,1);
                }
            }
            addedge(i*2,i*2+1,1);
        }
        for(int i=0;i<N;++i)
        {
            scanf("%s",sta);
            for(int j=0;j<D;++j)
            {
                if(sta[j]=='Y')
                {
                    addedge(i*2+1,N*2+F+j,1);
                }
            }
        }
        int ans=maxflow(start,end);
        printf("%d\n",ans);
    }
    return 0;
}