最大流。
这东西好像叫三分图匹配。
源点向每个食物点连一条容量为1的边。
每个饮料点向汇点连一条容量为1的边。
将每个牛点拆点，食物点向喜欢它的牛的入点连一条容量为1的边，牛的出点向它喜欢的饮料点连一条容量为1的边。
最大流即为答案，每头牛拆点是为了保证每头牛只有一种食物和一种饮料。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int dian=;
const int bian=;
const int INF=0x3f3f3f3f;
int h[dian],ver[bian],val[bian],nxt[bian],ch[dian],cr[dian];
int n,m,k,tot,aa,bb,cc;
int S,T;
void add(int a,int b,int c){
tot++;ver[tot]=b;val[tot]=c;nxt[tot]=h[a];h[a]=tot;
tot++;ver[tot]=a;val[tot]=;nxt[tot]=h[b];h[b]=tot;
}
bool tell(){
memset(ch,-,sizeof(ch));
queue<int>q;
q.push(S);
ch[S]=;
while(!q.empty()){
int t=q.front();
q.pop();
for(int i=h[t];i;i=nxt[i])
if(ch[ver[i]]==-&&val[i]){
ch[ver[i]]=ch[t]+;
q.push(ver[i]);
}
}
return ch[T]!=-;
}
int zeng(int a,int b){
if(a==T)
return b;
int r=;
for(int i=cr[a];i&&b>r;i=nxt[i])
if(ch[ver[i]]==ch[a]+&&val[i]){
int t=zeng(ver[i],min(b-r,val[i]));
val[i]-=t,r+=t,val[i^]+=t;
if(val[i])
cr[a]=i;
}
if(!r)
ch[a]=-;
return r;
}
int dinic(){
int r=,t;
while(tell()){
for(int i=;i<=n+n+m+k+;i++)
cr[i]=h[i];
while(t=zeng(S,INF))
r+=t;
}
return r;
}
int main(){
memset(h,,sizeof(h));
memset(nxt,,sizeof(nxt));
tot=;
scanf("%d%d%d",&n,&m,&k);
S=n+n+m+k+,T=n+n+m+k+;
for(int i=;i<=m;i++)
add(S,i,);
for(int i=;i<=k;i++)
add(m+n+n+i,T,);
for(int i=;i<=n;i++)
add(m+i,m+n+i,);
for(int i=;i<=n;i++){
scanf("%d%d",&aa,&bb);
for(int j=;j<=aa;j++){
scanf("%d",&cc);
add(cc,m+i,);
}
for(int j=;j<=bb;j++){
scanf("%d",&cc);
add(m+n+i,m+n+n+cc,);
}
}
printf("%d",dinic());
return ;
}
另，做这道题是因为今天考了一场试，网络流专题。
大爷看我们太弱没敢出太难，然后时间减了点，四个小时。
然后我脑残没打输入输出文件，爆零了。
赶紧打上，打上之后呢，还是爆零了。
其实就是一道都不会。
……
……
……
其实第一题不是很难，大概就是本题的加强版。
给一个n*m的矩形，有一些坏点，所有i行j列的非坏点，若i+j为偶数，则该点封印着一个恶魔。其他非坏点可以放置一个魔法水晶，魔法水晶能向且只能向相邻的一个点施法。对于一个恶魔，如果与它相邻的两个成直角的水晶同时向它施法，他就无法逃脱封印。问最多让多少恶魔无法逃脱封印。
1<=n,m<=50.
边想边写搞了两个小时，当我发现我的第六个建图是错的的时候，我就放弃了整场考试。
这题转化一下就是刚才的模型了。
考虑成直角的充要条件是左右中选一个，上下中选一个。所以就是对于一个恶魔点，总要选一个奇数行（列）的点和一个偶数行（列）的点。
这不就是食物和饮料嘛，源点连奇行点，偶行点连汇点，中间拆点然后相邻点连边，最大流完事。
主要就是要看出点间这种二分图关系。