/*因为牛的容量为1,把牛拆点 按照s->f->cow->cow->d->t建图 */#include#include #include #include using namespace std;#define inf 0x3f3f3f3f#define maxn 10005struct Edge{ int to,nxt,c;}e[maxn<<1];int head[maxn],tot,n,f,dd,s,t;void init(){memset(head,-1,sizeof head);tot=0;}void add(int u,int v,int c){ e[tot].to=v;e[tot].c=c;e[tot].nxt=head[u];head[u]=tot++; e[tot].to=u;e[tot].c=0;e[tot].nxt=head[v];head[v]=tot++;}int d[maxn];bool bfs(){ //在残量网络上构造分层图 memset(d,0,sizeof d); queue q; while(q.size())q.pop(); q.push(s);d[s]=1; while(q.size()){ int x=q.front();q.pop(); for(int i=head[x];i!=-1;i=e[i].nxt){ int y=e[i].to; if(d[y] || e[i].c==0)continue; q.push(y); d[y]=d[x]+1; if(y==t)return 1; } } return 0;}int dfs(int x,int flow){ if (x==t)return flow; int rest=flow; for(int i=head[x];i!=-1 && rest>0;i=e[i].nxt){ int y=e[i].to; if(e[i].c==0 || d[y]!=d[x]+1)continue; int k=dfs(y,min(rest,e[i].c)); if(!k) d[y]=0; //y点已经被增广完毕,本次dinic时不会再访问这个点 e[i].c-=k; e[i^1].c+=k; rest-=k; } return flow-rest;} int dinic(){ int ans=0; while(bfs()) while(int flow=dfs(s,inf)) ans+=flow; return ans;}/*牛编号[1,2*n],食物编号[2*n+1,n*2+f],饮料编号[2*n+f+1,2*n+f+d]*/int main(){ init(); cin>>n>>f>>dd; s=0;t=2*n+f+dd+1; for(int i=1;i<=f;i++)add(s,2*n+i,1); for(int i=1;i<=dd;i++)add(2*n+f+i,t,1); for(int i=1;i<=n;i++){ int k1,k2,F,D; cin>>k1>>k2; add(i,i+n,1);//拆点 while(k1--){ cin>>F; add(2*n+F,i,1); } while(k2--){ cin>>D; add(i+n,2*n+f+D,1); } } cout< <<'\n';}