建超级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('\n');}return 0; }
