非常非常经典的构图
有二分图学习基础的话，很容易想到这是一个“三分图”的匹配问题
我们将牛，food，drink作为点
为了方便，我们将牛放在中间，每头牛的出边指向drink种类，入边由food指入
建立超级源点指向所有food，超级汇点指向所有drink，
要满足最多的牛，也就是求一个最大流
但注意，如果这样求最大流的话，会经过牛点不止一次（因为牛会有多个入边和多个出边）
所以我们考虑将牛点拆为两个点，中间流量为1，这样就能保证牛只经过1次了
const max=;
var a:array[..,..] of longint;
numh,h,cur,pre:array[..] of longint;
n,t,i,j,m,s,f,d,ans,x:longint; procedure sap;
var i,j,flow,tmp,neck,u,k:longint;
begin
numh[]:=;
u:=;
while h[]<t+ do
begin
if u=t then
begin
i:=;
j:=cur[];
flow:=max;
while i<>t do //其实这个地方多余了，容易知道，瓶颈边的流量一定为1
begin
if flow>a[i,j] then
begin
neck:=i;
flow:=a[i,j];
end;
i:=j;
j:=cur[j];
end;
inc(ans,flow);
i:=;
j:=cur[i];
while i<>t do
begin
dec(a[i,j],flow);
inc(a[j,i],flow);
i:=j;
j:=cur[i];
end;
u:=neck;
end;
k:=-;
for i:= to t do
if (a[u,i]>) and (h[u]=h[i]+) then
begin
k:=i;
break;
end;
if k<>- then
begin
cur[u]:=k;
pre[k]:=u;
u:=k;
end
else begin
dec(numh[h[u]]);
if numh[h[u]]= then break; //GAP优化
tmp:=t+;
for i:= to t do
if (a[u,i]>) then tmp:=min(tmp,h[i]); //更新标号
h[u]:=tmp+;
inc(numh[h[u]]);
if u<> then u:=pre[u];
end;
end;
end; begin
readln(n,m,s);
fillchar(a,sizeof(a),);
t:=*n+m+s+; //计算建图后总点数
for i:= to m do
a[,*n+i]:=;
for i:= to s do
a[*n+m+i,t]:=;
for i:= to n do
a[i,i+n]:=;
for i:= to n do
begin
read(f,d);
for j:= to f do
begin
read(x);
a[*n+x,i]:=;
end;
for j:= to d do
begin
read(x);
a[i+n,*n+m+x]:=;
end;
end;
fillchar(cur,sizeof(cur),);
fillchar(pre,sizeof(pre),);
fillchar(h,sizeof(h),);
fillchar(numh,sizeof(numh),);
sap;
writeln(ans);
end.
这题带给我们两个启示：
拆点和建立超级源汇点是网络流构图的基础而又重要的部分
网络流的建图比较复杂（这题还算简单），要细心检查……；