/*
因为牛的容量为1，把牛拆点
按照s->f->cow->cow->d->t建图
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
#define inf 0x3f3f3f3f
#define maxn 10005
struct 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<
int>
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<<dinic()<<
'\n';
}
转载于:https://www.cnblogs.com/zsben991126/p/11003128.html
