非常好的网络流
每个顾客分别用一个结点来表示。
对于每个猪圈的第一个顾客，从源点向他连一条边，容量就是该猪圈里的猪的初始数量
对于每个猪圈，假设有n个顾客打开过它，则对所有整数i∈[1, n)，从该猪圈的第i个顾客向第i + 1个顾客连一条边，容量为无穷。
从各个顾客到汇点各有一条边，容量是各个顾客能买的数量上限。
其实很好理解
const inf=;
type node=record
from,point,flow,next:longint;
end;
var p,s,w,h,numh,cur,pre:array[..] of longint;
v:array[..] of boolean;
a:array[..,..] of longint;
edge:array[..] of node;
ans,z,len,t,i,j,k,x,y,n,m:longint; procedure add(x,y,f:longint);
begin
inc(len);
edge[len].from:=x;
edge[len].point:=y;
edge[len].flow:=f;
edge[len].next:=p[x];
p[x]:=len;
end; procedure sap;
var q,u,i,j,flow,neck,tmp:longint;
begin
fillchar(numh,sizeof(numh),);
fillchar(h,sizeof(h),);
fillchar(pre,sizeof(pre),);
numh[]:=t+;
u:=;
while h[]<t+ do
begin
if u=t then
begin
neck:=;
flow:=inf;
i:=;
j:=cur[i];
while i<>t do
begin
if flow>edge[j].flow then
begin
flow:=edge[j].flow;
neck:=i;
end;
i:=edge[j].point;
j:=cur[i];
end;
i:=;
j:=cur[i];
while i<>t do
begin
dec(edge[j].flow,flow);
inc(edge[j xor ].flow,flow);
i:=edge[j].point;
j:=cur[i];
end;
ans:=ans+flow;
u:=neck;
end;
q:=-;
i:=p[u];
while i<>- do
begin
x:=edge[i].point;
if (edge[i].flow>) and (h[u]=h[x]+) then
begin
q:=i;
break;
end;
i:=edge[i].next;
end;
if q<>- then
begin
cur[u]:=q;
pre[x]:=u;
u:=x;
end
else begin
dec(numh[h[u]]);
if numh[h[u]]= then break;
tmp:=t+;
i:=p[u];
while i<>- do
begin
x:=edge[i].point;
if (edge[i].flow>) then tmp:=min(tmp,h[x]);
i:=edge[i].next;
end;
h[u]:=tmp+;
inc(numh[h[u]]);
if u<> then u:=pre[u];
end;
end;
end; begin
readln(m,n);
fillchar(p,sizeof(p),);
len:=-;
t:=n+;
for i:= to m do
read(w[i]);
for i:= to n do
begin
read(y);
z:=;
for j:= to y do
begin
read(x);
if v[x]=false then
begin
v[x]:=true;
z:=z+w[x]; //如果多条边连接源点和顾客，那么合并
end;
inc(s[x]);
a[x,s[x]]:=i;
end;
if z<> then
begin
add(,i,z);
add(i,,);
end;
readln(x);
add(i,t,x);
add(t,i,);
end;
for i:= to m do
for j:= to s[i]- do
for k:=j+ to s[i] do
begin
add(a[i,j],a[i,k],inf);
add(a[i,k],a[i,j],);
end;
sap;
writeln(ans);
end.