B – 编程知识网

题目大意：有一群牛，还有一些牛喜欢的食物和喜欢的饮料，不过这些牛都很特别，他们不会与别的牛吃同一种食物或者饮料，现在约翰拿了一些食物和饮料，同时他也知道这些牛喜欢的食物和饮料的种类，求出来最多能让多少头牛吃上食物还并且喝饮料。

输入分析：输入的第一行是N F D，分别是牛，食物，饮料的个数。下面N行，每行开始的前两个数分别是Fi，Di表示第i头牛喜欢的食物和饮料的个数，紧跟着输入Fi种食物和Di种饮料。

分析：看到这里很容易就可以想到用牛与食物建立关系，并且让牛同时与饮料建立关系（把牛放在中间，仔细想一下为什么）。不过这样很明显也会出现问题，比如下面（图1），因为只能满足一头牛，所以为了不出现这种错误，我们需要把牛拆开，中间再加一条边让他们的最大承受流量是1（图2），这样不管有多少与它相连他中间只能经过流量 1，再添加一个源点和汇点。这样就可以用最大流解决了。

(图1)

（图2）

ps：写dinic给残余网络分层的时候用了if,然后调试了很久很久。。。。发现后心中有十万头草泥马狂奔而过，还是要细心才是**************************************************************************************************************************************************#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;

const int MAXN = 407;
const int oo = 1e9+7;

int G[MAXN][MAXN], layer[MAXN];

bool bfs(int start, int End)
{
    bool used[MAXN]={0};
    queue<int> Q;Q.push(start);
    memset(layer, –1, sizeof(layer));
    layer[start] = 0, used[start] = true;

    while(Q.size())
    {
        int u = Q.front();Q.pop();

if(u == End)return true;

        for(int i=1; i<=End; i++)
        {
            if(G[u][i] && used[i] == false)
            {
                used[i] = true;
                layer[i] = layer[u]+1;
                Q.push(i);
            }
        }
    }

return false;
}
int dfs(int u, int MaxFlow, int End)
{
if(u == End)return MaxFlow;

int uFlow = 0;

    for(int i=1; i<=End; i++)
    {
        if(G[u][i] && layer[i]==layer[u]+1)
        {
            int flow = min(MaxFlow-uFlow, G[u][i]);
            flow = dfs(i, flow, End);

            G[u][i] -= flow;
            G[i][u] += flow;
            uFlow += flow;

            if(uFlow == MaxFlow)
                break;
        }
    }

return uFlow;
}
int dinic(int start, int End)
{
int MaxFlow = 0;

while( bfs(start, End) == true )
MaxFlow += dfs(start, oo, End);

return MaxFlow;
}

int main()
{
int N, F, D;

    while(scanf(“%d%d%d“, &N, &F, &D) != EOF)
    {///拆点后牛开始位置，源点和汇点
        int Ni = N+F+D, start = Ni+N+1, End = start+1;

int i, j, x, Di, Fi;

memset(G, 0, sizeof(G));

        for(i=1; i<=N; i++)
        {///食物放在前面，牛放在中间，饮料放在最后面

            scanf(“%d%d“, &Fi, &Di);
            for(j=1; j<=Fi; j++)
            {///这头牛喜欢的食物,牛的区间在F~N+F
                scanf(“%d“, &x);
                G[x][F+i] = true;///用食物连接牛
            }
            for(j=1; j<=Di; j++)
            {///这头牛喜欢的饮料，饮料的区间在 F+N~F+N+D
                scanf(“%d“, &x);
                G[Ni+i][F+N+x] = true;///用拆的点连接
            }
        }

        for(i=1; i<=N; i++)///建立牛和拆点的关系
            G[F+i][Ni+i] = true;
        for(i=1; i<=F; i++)///建立源点和食物的关系
            G[start][i] = true;
        for(i=1; i<=D; i++)///建立饮料喝汇点的关系
            G[F+N+i][End] = true;