poj 3281

建超级s向每个食物连容量为1的边，超级汇点t；

　　　　每个饮料向t连容量为1的边，将每头牛拆点，一个连该牛喜欢的食物，另一点连该牛喜欢的饮料，俩个点相连，容量均为1；

　　　　ans=跑一遍最大流

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
int mi(int x,int y){
    return x<y?x:y;
}
inline int read(){
    int sum=0,x=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            x=0;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar();
    }
    //cout<<"~~"<<endl;
    return x?sum:-sum;
}
inline void write(int x){
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}
const int M=502;
const int inf=0x3f3f3f3f;
struct node{
    int v,w,nextt;
}e[200003];
int head[M],cur[M],deep[M],tot,s,t;
void addedge(int u,int v,int w){
    e[tot].v=v;
    e[tot].w=w;
    e[tot].nextt=head[u];
    head[u]=tot++;
    e[tot].v=u;
    e[tot].w=0;
    e[tot].nextt=head[v];
    head[v]=tot++;
}
bool bfs(){
    for(int i=0;i<=t;i++)
        deep[i]=0;
    queue<int>que;
    que.push(s);
    deep[s]=1;
    while(!que.empty()){
        int u=que.front();
        que.pop();
        for(int i=head[u];~i;i=e[i].nextt){
            int v=e[i].v;
            if(e[i].w>0&&deep[v]==0){
                deep[v]=deep[u]+1;
                if(v==t)
                    return true;
                que.push(v);
            }
        }
    }
    return deep[t]==0?false:true;
}
int dfs(int u,int fl){
    if(u==t)
        return fl;
    int ans=0,x;
    for(int i=cur[u];~i;i=e[i].nextt){
        int v=e[i].v;
        if(e[i].w>0&&deep[v]==deep[u]+1){
            x=dfs(v,mi(fl-ans,e[i].w));
            e[i].w-=x;
            e[i^1].w+=x;
            ans+=x;
            if(e[i].w)
                cur[u]=i;
            if(ans==fl)
                return ans;
        }
    }
    if(ans==0)
        deep[u]=0;
    return ans;
}
int dinic(){
    int ans=0;
    while(bfs()){
        for(int i=0;i<=t;i++)
            cur[i]=head[i];
        ans+=dfs(s,inf);
    }
    return ans;
}
int n,f,d;
void init(){
    s=0;
    t=f+2*n+d+1;
    tot=0;
    for(int i=0;i<=t;i++)
        head[i]=-1;
}
int main(){
    while(~scanf("%d%d%d",&n,&f,&d)){
        init();
    //    cout<<t<<endl;
        for(int i=1;i<=f;i++)
            addedge(s,i,1);
        for(int i=2*n+f+1;i<t;i++)
            addedge(i,t,1);
        for(int i=1;i<=n;i++){//cout<<n<<"@@"<<f<<"@@"<<d<<endl;
            addedge(f+i,f+n+i,1);
            int f1=read(),d1=read();
        //    cout<<f1<<"!!!"<<d1<<endl;
            for(int j=1;j<=f1;j++){
                int ff=read();
                addedge(ff,f+i,1);
            }
            
            for(int j=1;j<=d1;j++){
                int dd=read();
                addedge(f+n+i,2*n+f+dd,1);
            //    cout<<2*n+f+dd<<endl;
            }
        }
        write(dinic());
        putchar('
');
    }
    return 0;
}