Dining

poj3281：http://poj.org/problem?id=3281

题意：有n个人，然后有F份食物，D份饮料，然后每一个会有一些喜爱的饮料和食物，问你最多可以使得多少人同时得到一份自己喜爱的食物和一份饮料。

题解：很明显，要拆点。食物要拆成两个点，饮料也要拆成两个点，人也要拆成两个点，然后设置源点和汇点，源点和食物，食物和人，人和饮料，饮料和汇点分别建立一边。

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cstdio>

 #include<queue>

 #define INF 100000000

 using namespace std;

 const int N=;

 const int M=;

 struct Node{

    int v;

    int f;

    int next;

 }edge[M];

 int n,m,u,v,cnt,sx,ex;

 int head[N],pre[N];

 int val[N][];//根据题目要求申请

 void init(){

     cnt=;

     memset(head,-,sizeof(head));

 }

 void add(int u,int v,int w){

     edge[cnt].v=v;

     edge[cnt].f=w;

     edge[cnt].next=head[u];

     head[u]=cnt++;

     edge[cnt].f=;

     edge[cnt].v=u;

     edge[cnt].next=head[v];

     head[v]=cnt++;

 }

 bool BFS(){

   memset(pre,,sizeof(pre));

   pre[sx]=;

   queue<int>Q;

   Q.push(sx);

  while(!Q.empty()){

      int d=Q.front();

      Q.pop();

      for(int i=head[d];i!=-;i=edge[i].next    ){

         if(edge[i].f&&!pre[edge[i].v]){

             pre[edge[i].v]=pre[d]+;

             Q.push(edge[i].v);

         }

      }

   }

  return pre[ex]>;

 }

 int dinic(int flow,int ps){

     int f=flow;

      if(ps==ex)return f;

      for(int i=head[ps];i!=-;i=edge[i].next){

         if(edge[i].f&&pre[edge[i].v]==pre[ps]+){

             int a=edge[i].f;

             int t=dinic(min(a,flow),edge[i].v);

               edge[i].f-=t;

               edge[i^].f+=t;

             flow-=t;

              if(flow<=)break;

         }

      }

       if(f-flow<=)pre[ps]=-;

       return f-flow;

 }

 int solve(){

     int sum=;

     while(BFS())

         sum+=dinic(INF,sx);

     return sum;

 }

 int d,f,k1,k2,temp;

 int main() {

     while(~scanf("%d%d%d",&n,&f,&d)){

         init();

     for(int i=;i<=n;i++){

         scanf("%d%d",&k1,&k2);

         for(int j=;j<=k1;j++){

               scanf("%d",&temp);

               add(*n+*d+f+temp,i,);

         }

         for(int j=;j<=k2;j++){

               scanf("%d",&temp);

               add(n+i,*n+temp,);

         }

         add(i,i+n,);

     }

     for(int i=;i<=f;i++){

        add(*n+*d+i,*n+*d+f+i,);

        add(,*n+*d+i,);

     }

     for(int i=;i<=d;i++){

         add(*n+i,*n+d+i,);

         add(*n+d+i,*n+*d+*f+,);

     }

       sx=;ex=*n+*d+*f+;

       printf("%d\n",solve());

     }

     return ;

 }