首页 > ACM题库 > HDU-杭电 > HDU 4292-Food[解题报告]HOJ
2015
05-23

HDU 4292-Food[解题报告]HOJ

Food

问题描述 :

  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.

输入:

  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).

输出:

  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).

样例输入:

4 3 3
1 1 1
1 1 1
YYN
NYY
YNY
YNY
YNY
YYN
YYN
NNY

样例输出:

3

#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

// the maximum number of vertices
#define NN 802

// adjacency matrix (fill this up)
// If you fill adj[][] yourself, make sure to include both u->v and v->u.
int cap[NN][NN], deg[NN], adj[NN][NN];

// BFS stuff
int q[NN], prev[NN];

int dinic( int n, int s, int t )
{
    int flow = 0;

    while( true )
    {
        // find an augmenting path
        memset( prev, -1, sizeof( prev ) );
        int qf = 0, qb = 0;
        prev[q[qb++] = s] = -2;
        while( qb > qf && prev[t] == -1 )
            for( int u = q[qf++], i = 0, v; i < deg[u]; i++ )
                if( prev[v = adj[u][i]] == -1 && cap[u][v] )
                    prev[q[qb++] = v] = u;

        // see if we're done
        if( prev[t] == -1 ) break;

        // try finding more paths
        for( int z = 0; z < n; z++ ) if( cap[z][t] && prev[z] != -1 )
        {
            int bot = cap[z][t];
            for( int v = z, u = prev[v]; u >= 0; v = u, u = prev[v] )
                bot = min(bot, cap[u][v]);
            if( !bot ) continue;

            cap[z][t] -= bot;
            cap[t][z] += bot;
            for( int v = z, u = prev[v]; u >= 0; v = u, u = prev[v] )
            {
                cap[u][v] -= bot;
                cap[v][u] += bot;
            }
            flow += bot;
        }
    }

    return flow;
}

int n, f, d;

int main(void)
{
	while(scanf("%d %d %d", &n, &f, &d) != -1)
	{
		memset(cap, 0, sizeof(cap));
		int start = f + d + n * 2, end = f + d + 1 + n * 2;
		int foodBase = n * 2;
		int drinkBase = foodBase + f;

		for(int i=0;i<n;i++) cap[i][n + i] = 1;
		for(int i=0;i<f;i++)
		{
			int curFood;
			scanf("%d", &curFood);
			cap[start][foodBase + i] = curFood;
		}
		for(int i=0;i<d;i++)
		{
			int curDrink;
			scanf("%d", &curDrink);
			cap[drinkBase + i][end] = curDrink;
		}

		for(int i=0;i<n;i++)
		{
		 	char str[201];
			scanf("%s", str);
			for(int j=0;j<f;j++) if(str[j] == 'Y') cap[foodBase + j][i] = 1;
		}

		for(int i=0;i<n;i++)
		{
			char str[201];
			scanf("%s", str);
			for(int j=0;j<d;j++) if(str[j] == 'Y') cap[i + n][drinkBase + j] = 1;
		}

 		memset( deg, 0, sizeof( deg ) );
    	for( int u = 0; u <= end; u++ )
        	for( int v = 0; v <= end; v++ ) if( cap[u][v] || cap[v][u] )
            	adj[u][deg[u]++] = v;
		

		printf( "%d\n", dinic( end + 1, start, end ) );
	}

	return 0;
}