网络流 拆点 食物与饮料的分配

题目链接：http://poj.org/problem?id=3281
题目大意：有N头牛，F种食物，D种饮料，每头牛都有自己喜欢的食物和饮料，每种饮料和食物只能分配给一头牛，一头牛只能吃一种饮料和食物。问：最多有多少头牛能同时得到自己喜欢的食物和饮料。

思路：一头牛必须同时获得一个食物和一个饮料才能满足。一头牛只能吃一种饮料和食物。问至多有多少头牛可以获得满足。相当的是二分图匹配。但是明显不行，因为要分配两个东西，两个东西还要同时满足。

最大流建图：食物和饮料放在两端，源点连所有的食物，权值为1。
饮料连所有的水，权值为1。把牛拆点，左点连食物，右点连饮料。

如果一头牛需要k种食物和k种饮料。那么左点到右点连一条权值为k的边。这里k=1。然后根据牛的喜好食物与左点和右点和饮料连边。
然后跑最大流。

为什么要拆点？如果不拆点：

虽然满足了每种饮料和食物只能分配给一头牛。但是没有满足一头牛只能吃一种饮料和食物。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>

using namespace std;
const int maxn=1e5+10;
const int maxm=2e5+10;

struct E
{
    int v;   //每一条边指向的点
    int next;//指向对应点的前一条边
    int w;   //每一条边的残量

}e[maxm];

int s, t;//源点和汇点
int cut;//边的数量，从0开始编号
int head[maxm];//每一个点最后一条边的编号
int d[maxn];//分层图中标记深度
int inf=(1<<31)-1;
int cur[maxn];//cur就是记录当前点u循环到了哪一条边
vector<int> F[105], D[105];

void init()
{
    cut=-1;
    memset(head, -1, sizeof(head));
    for(int i=0;i<105;i++)
    {
        F[i].clear(), D[i].clear();
    }
}

void addEdge(int u, int v, int w)
{
    cut++;
    e[cut].next=head[u];
    e[cut].v=v;
    e[cut].w=w;
    head[u]=cut;
}

void add(int u, int v, int w)
{
    addEdge(u, v, w);
    addEdge(v, u, 0);
}

int bfs()
{
    queue<int> q;
    while(!q.empty())
    {
        q.pop();
    }
    memset(d, 0, sizeof(d));
    d[s]=1;//源点深度为1
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=-1;i=e[i].next)
        {
            int v=e[i].v, w=e[i].w;
            if(w>0&&d[v]==0)//若该残量不为0，且V[i]还未分配深度，则给其分配深度并放入队列
            {
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
    if(d[t]==0)//当汇点的深度不存在时，说明不存在分层图，同时也说明不存在增广路
    {
        return 0;
    }

    return 1;
}

int dfs(int u, int dis)//u是当前节点，dist是当前流量
{
    if(u==t)
    {
        return dis;//当已经到达汇点，直接返回
    }

    for(int &i=cur[u];i!=-1;i=e[i].next)
    {
        int v=e[i].v, w=e[i].w;
        if((d[v]==d[u]+1)&&w!=0)//注意这里要满足分层图和残量不为0两个条件
        {
            int di=dfs(v, min(dis, w));//向下增广
            if(di>0)//若增广成功
            {
                e[i].w-=di;//正向边减
                e[i^1].w+=di;//反向边加
                return di;//向上传递
            }
        }
    }

    return 0;//否则说明没有增广路，返回0
}

int Dinic()
{
    int ans=0;//记录最大流量
    while (bfs())
    {
        for(int i=s;i<=t;i++)//每一次建立完分层图后都要把cur置为每一个点的第一条边
        {
            cur[i]=head[i];
        }
        while (int d=dfs(s,inf))
        {
            ans+=d;
        }
    }
    return ans;
}

int main()
{
    int n, f, d;

    while(~scanf("%d%d%d",&n,&f,&d))
    {
        init();
        for(int i=1;i<=n;i++)
        {
            int a, b, c, d;
            scanf("%d%d",&a,&b);
            for(int j=0;j<a;j++)
            {
                scanf("%d",&c);
                F[i].push_back(c);
            }
            for(int j=0;j<b;j++)
            {
                scanf("%d",&d);
                D[i].push_back(d);
            }
        }
        for(int i=1;i<=n;i++)
        {
            add(f+i, f+n+i, 1);
            for(int j=0;j<F[i].size();j++)
            {
                add(F[i][j], f+i, 1);
            }
            for(int j=0;j<D[i].size();j++)
            {
                add(f+n+i, f+2*n+D[i][j], 1);
            }
        }
        for(int i=1;i<=f;i++)
        {
            add(0, i, 1);
        }
        for(int i=1;i<=d;i++)
        {
            add(f+2*n+i, f+2*n+d+1, 1);
        }
        s=0, t=f+2*n+d+1;
        cout<<Dinic()<<endl;
    }

    return 0;
}