POJ 3281 Dining

POJ 3281 Dining

題目概述:腦書p.239

有N頭牛，F種食物，D種飲料。每一頭牛只喝自己最愛的某些食物跟飲料，而每一種食物跟飲料只能給一頭牛吃。求吃到食物且喝到飲料的牛樹最大值。

思路:

詳見腦書。

待補。

AC code:

//By SCJ

#include<iostream>

#include<cstring>

#include<vector>

using namespace std;

#define endl '\n'

#define INF 100000000

int N,F,D,END;

struct Edge{

   int to,cap,rev;

   Edge(int _to,int _cap,int _rev)

   {

       to=_to;cap=_cap;rev=_rev;

   }

};

vector<Edge> G[500];

void add_Edge(int from,int to,int cap)

{

   G[from].push_back(Edge(to,cap,G[to].size()));

   G[to].push_back(Edge(from,0,G[from].size()-1));

}

bool used[500];

int dfs(int v,int f)

{

   used[v]=1;

   if(v==END) return f;

   //cout<<"DFS v="<<v<<endl;

   for(int i=0;i<G[v].size();++i)

   {

       Edge &e=G[v][i];

       if(e.cap>0&&used[e.to]==0)

       {

           int d=dfs(e.to,min(f,e.cap));

           if(d>0)

           {

               e.cap-=d;

               G[e.to][e.rev].cap+=d;

               return d;

           }

       }

   }

   return 0;

}

int max_flow()

{

   int res=0,d;

   memset(used,0,sizeof(used));

   while(d=dfs(0,INF)) res+=d,memset(used,0,sizeof(used));

   return res;

}

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   cin>>N>>F>>D;

   END=2*N+F+D+1;

   for(int i=1;i<=N;++i)

   {

       int a,b,tp;cin>>a>>b;

       for(int k=0;k<a;++k)

       {

           cin>>tp;

           add_Edge(2*N+tp,i,1);

       }

       for(int k=0;k<b;++k)

       {

           cin>>tp;

           add_Edge(N+i,2*N+F+tp,1);

       }

   }

   for(int i=1;i<=N;++i)

       add_Edge(i,i+N,1);

   for(int i=1;i<=F;++i)

       add_Edge(0,2*N+i,1);

   for(int i=1;i<=D;++i)

       add_Edge(2*N+F+i,END,1);

   cout<<max_flow()<<endl;

}