//#include<bits/stdc++.h>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<queue>
#include<iostream>
using namespace std;
#define ll long long
#define pb push_back
const int maxn=500;
const int inf=0x3f3f3f3f;
struct Edge{
int from,to,cap,flow;
Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}
};
int n,m;
vector<Edge>edges;
vector<int>G[maxn];//G[i][j]:i点第j条边在edges数组编号
int a[maxn];//起点到i的可增大量
int p[maxn];//最短路树上p的入弧编号
void init(){
for(int i=0;i<n;i++)G[i].clear();
edges.clear();
}
void addedge(int u,int v,int cap){
edges.pb(Edge(u,v,cap,0));
edges.pb(Edge(v,u,0,0));
m=edges.size();
G[u].pb(m-2);
G[v].pb(m-1);
}
int maxflow(int s,int t){
int flow=0;
while(1){//不断尝试找增广路
memset(a,0,sizeof(a));
queue<int>q;
q.push(s);
a[s]=inf;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=0;i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if(!a[e.to] && e.cap>e.flow){
p[e.to]=G[x][i];
a[e.to]=min(a[x],e.cap-e.flow);
q.push(e.to);
}
}
if(a[t])break;
}
if(!a[t])break;
for(int u=t;u!=s;u=edges[p[u]].from){
edges[p[u]].flow+=a[t];//增广路在变少
edges[p[u]^1].flow-=a[t];
}
flow+=a[t];
}
return flow;
}
int main(){
int N,F,D;
while(~scanf("%d %d %d",&N,&F,&D)){
n=F+D+N+N+1;
init();
int start=0;int end=n;
for(int i=1;i<=F;i++)addedge(start,i,1);
for(int i=F+N+N+1;i<=F+N+N+D;i++)addedge(i,end,1);
for(int i=1;i<=N;i++)addedge(F+2*i-1,F+2*i,1);//牛拆点连通
int k1,k2;
int x;
for(int i=1;i<=N;i++){
scanf("%d %d",&k1,&k2);
while(k1--){
scanf("%d",&x);
addedge(x,F+2*i-1,1);
}
while(k2--){
scanf("%d",&x);
addedge(F+2*i,F+2*N+x,1);
}
}
printf("%d\n",maxflow(start,end));
}
}
听说ek慢，邻接矩阵的数据范围之外就不靠谱了。。不过又似乎都跑去用dicnic了，那这代码我也就不去精简了。。（
最大流的解题过程就是用bfs在当前网络上寻找增广路，队列枚举点跑完之后观察到终点有没有增量
有的话记录答案，往管道里再加水，然后再找增广路。。。
这题用到了拆点的做法，一只牛分成两个点，一个连向食物一个连向水
一般网络流的拆点是为了限制点的流量来着，这条拆点的原因
看网上说是为了防止一只牛占用多个食物，所以食物→牛→牛→饮料，中间限流一下