【POJ1149&BZOJ1280】PIGS（最大流）

  1 var head,vet,next,len,dis,gap,fan:array[0..110000]of longint;
  2     a,last:array[1..10000]of longint;
  3     m,n,i,j,x,y,z,tot,s,source,src:longint;
  4 
  5 procedure add(a,b,c:longint);
  6 begin
  7  inc(tot);
  8  next[tot]:=head[a];
  9  vet[tot]:=b;
 10  len[tot]:=c;
 11  head[a]:=tot;
 12 
 13  inc(tot);
 14  next[tot]:=head[b];
 15  vet[tot]:=a;
 16  len[tot]:=0;
 17  head[b]:=tot;
 18 end;
 19 
 20 function min(x,y:longint):longint;
 21 begin
 22  if xthen exit(x);
 23  exit(y);
 24 end;
 25 
 26 function dfs(u,aug:longint):longint;
 27 var e,v,t,flow,val:longint;
 28 begin
 29  if u=src then exit(aug);
 30  e:=head[u]; flow:=0; val:=s-1;
 31  while e<>0 do
 32  begin
 33   v:=vet[e];
 34   if len[e]>0 then
 35   begin
 36    if dis[u]=dis[v]+1 then
 37    begin
 38     t:=dfs(v,min(len[e],aug-flow));
 39     len[e]:=len[e]-t;
 40     len[fan[e]]:=len[fan[e]]+t;
 41     flow:=flow+t;
 42     if dis[source]>=s then exit(flow);
 43     if aug=flow then break;
 44    end;
 45    val:=min(val,dis[v]);
 46   end;
 47   e:=next[e];
 48  end;
 49  if flow=0 then
 50  begin
 51   dec(gap[dis[u]]);
 52   if gap[dis[u]]=0 then dis[source]:=s;
 53   dis[u]:=val+1;
 54   inc(gap[dis[u]]);
 55  end;
 56  exit(flow);
 57 end;
 58 
 59 function maxflow:longint;
 60 var ans:longint;
 61 begin
 62  fillchar(gap,sizeof(gap),0);
 63  fillchar(dis,sizeof(dis),0);
 64  gap[0]:=s; ans:=0;
 65  while dis[source]do ans:=ans+dfs(source,maxlongint);
 66  exit(ans);
 67 end;
 68 
 69 begin
 70  assign(input,'bzoj1280.in'); reset(input);
 71  assign(output,'bzoj1280.out'); rewrite(output);
 72  readln(m,n);
 73  for i:=1 to m do read(a[i]);
 74  for i:=1 to 110000 do
 75   if i and 1=1 then fan[i]:=i+1
 76    else fan[i]:=i-1;
 77  source:=n+1; src:=n+2; s:=n+2;
 78  for i:=1 to n do
 79  begin
 80   read(x);
 81   for j:=1 to x do
 82   begin
 83    read(y);
 84    if last[y]=0 then
 85    begin
 86     add(source,i,a[y]);
 87     last[y]:=i;
 88    end
 89     else
 90     begin
 91      add(last[y],i,maxlongint);
 92      last[y]:=i;
 93     end;
 94   end;
 95   read(z);
 96   add(i,src,z);
 97  end;
 98  writeln(maxflow);
 99  close(input);
100  close(output);
101 end.