HDU 4292 Food(最大流)

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的边，将饮料与汇点建立流量为饮料数量的边，跑最大流即可。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define XDebug(x) cout<<#x<<"="<<x<<endl;
#define ArrayDebug(x,i) cout<<#x<<"["<<i<<"]="<<x[i]<<endl;
#define print(x) out(x);putchar('\n')
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int INF = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
template <class T>
inline bool read(T &ret) {
    char c;
    int sgn;
    if (c = getchar(), c == EOF) {
        return false;
    }
    while (c != '-' && (c < '0' || c > '9')) {
        c = getchar();
    }
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9') {
        ret = ret * 10 + (c - '0');
    }
    ret *= sgn;
    return true;
}
template <class T>
inline void out(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) {
        out(x / 10);
    }
    putchar(x % 10 + '0');
}

struct Link {
    int V, Weight, Next;
    Link(int _V = 0, int _Weight = 0, int _Next = 0): V(_V), Weight(_Weight), Next(_Next) {}
};

Link edges[200005];
int Head[maxn];
int Tot;
int Depth[maxn];
int Current[maxn];
int N, F, D;

void Init() {
    Tot = 0;
    memset(Head, -1, sizeof(Head));
}

void AddEdge(int U, int V, int Weight, int ReverseWeight = 0) {
    edges[Tot].V = V;
    edges[Tot].Weight = Weight;
    edges[Tot].Next = Head[U];
    Head[U] = Tot++;
    edges[Tot].V = U;
    edges[Tot].Weight = ReverseWeight;
    edges[Tot].Next = Head[V];
    Head[V] = Tot++;
}

bool Bfs(int Start, int End) {
    memset(Depth, -1, sizeof(Depth));
    std::queue<int> Que;
    Depth[Start] = 0;
    Que.push(Start);
    while (!Que.empty()) {
        int Vertex = Que.front();
        Que.pop();
        for (int i = Head[Vertex]; i != -1; i = edges[i].Next) {
            if (Depth[edges[i].V] == -1 && edges[i].Weight > 0) {
                Depth[edges[i].V] = Depth[Vertex] + 1;
                Que.push(edges[i].V);
            }
        }
    }
    return Depth[End] != -1;
}

int Dfs(int Vertex, int End, int NowFlow) {
    if (Vertex == End || NowFlow == 0) {
        return NowFlow;
    }
    int UsableFlow = 0, FindFlow;
    for (int &i = Current[Vertex]; i != -1; i = edges[i].Next) {
        if (edges[i].Weight > 0 && Depth[edges[i].V] == Depth[Vertex] + 1) {
            FindFlow = Dfs(edges[i].V, End, std::min(NowFlow - UsableFlow, edges[i].Weight));
            if (FindFlow > 0) {
                edges[i].Weight -= FindFlow;
                edges[i ^ 1].Weight += FindFlow;
                UsableFlow += FindFlow;
                if (UsableFlow == NowFlow) {
                    return NowFlow;
                }
            }
        }
    }
    if (!UsableFlow) {
        Depth[Vertex] = -2;
    }
    return UsableFlow;
}

int Dinic(int Start, int End) {
    int MaxFlow = 0;
    while (Bfs(Start, End)) {
        for (int i = 0; i <= F + N + N + D + 1; ++i) {
            Current[i] = Head[i];
        }
        MaxFlow += Dfs(Start, End, INF);
    }
    return MaxFlow;
}

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    char Accept[220];
    while (~scanf("%d%d%d", &N, &F, &D)) {
        Init();
        for (int i = 1, X; i <= F; ++i) {
            read(X);
            AddEdge(0, i, X);
        }
        for (int i = 1, X; i <= D; ++i) {
            read(X);
            AddEdge(F + N + N + i, F + N + N + D + 1, X);
        }
        for (int i = 1; i <= N; ++i) {
            AddEdge(F + i, F + N + i, 1);
            scanf("%s", Accept);
            for (int j = 1; j <= F; ++j) {
                if (Accept[j - 1] == 'Y') {
                    AddEdge(j, F + i, 1);
                }
            }
        }
        for (int i = 1; i <= N; ++i) {
            scanf("%s", Accept);
            for (int j = 1; j <= F; ++j) {
                if (Accept[j - 1] == 'Y') {
                    AddEdge(F + N + i, F + N + N + j, 1);
                }
            }
        }
        print(Dinic(0, F + N + N + D + 1));
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("gedit out.txt");
#endif
    return 0;
}