poj1149

非常好的网络流

每个顾客分别用一个结点来表示。

对于每个猪圈的第一个顾客，从源点向他连一条边，容量就是该猪圈里的猪的初始数量

对于每个猪圈，假设有n个顾客打开过它，则对所有整数i∈[1, n)，从该猪圈的第i个顾客向第i + 1个顾客连一条边，容量为无穷。

从各个顾客到汇点各有一条边，容量是各个顾客能买的数量上限。

其实很好理解

  1 const inf=100000007;
  2 type node=record
  3        from,point,flow,next:longint;
  4      end;
  5 var p,s,w,h,numh,cur,pre:array[0..1010] of longint;
  6     v:array[0..1010] of boolean;
  7     a:array[0..1010,0..1010] of longint;
  8     edge:array[0..1000010] of node;
  9     ans,z,len,t,i,j,k,x,y,n,m:longint;
 10 
 11 procedure add(x,y,f:longint);
 12   begin
 13     inc(len);
 14     edge[len].from:=x;
 15     edge[len].point:=y;
 16     edge[len].flow:=f;
 17     edge[len].next:=p[x];
 18     p[x]:=len;
 19   end;
 20 
 21 procedure sap;
 22   var q,u,i,j,flow,neck,tmp:longint;
 23   begin
 24     fillchar(numh,sizeof(numh),0);
 25     fillchar(h,sizeof(h),0);
 26     fillchar(pre,sizeof(pre),255);
 27     numh[0]:=t+1;
 28     u:=0;
 29     while h[0]<t+1 do
 30     begin
 31       if u=t then
 32       begin
 33         neck:=0;
 34         flow:=inf;
 35         i:=0;
 36         j:=cur[i];
 37         while i<>t do
 38         begin
 39           if flow>edge[j].flow then
 40           begin
 41             flow:=edge[j].flow;
 42             neck:=i;
 43           end;
 44           i:=edge[j].point;
 45           j:=cur[i];
 46         end;
 47         i:=0;
 48         j:=cur[i];
 49         while i<>t do
 50         begin
 51           dec(edge[j].flow,flow);
 52           inc(edge[j xor 1].flow,flow);
 53           i:=edge[j].point;
 54           j:=cur[i];
 55         end;
 56         ans:=ans+flow;
 57         u:=neck;
 58       end;
 59       q:=-1;
 60       i:=p[u];
 61       while i<>-1 do
 62       begin
 63         x:=edge[i].point;
 64         if (edge[i].flow>0) and (h[u]=h[x]+1) then
 65         begin
 66           q:=i;
 67           break;
 68         end;
 69         i:=edge[i].next;
 70       end;
 71       if q<>-1 then
 72       begin
 73         cur[u]:=q;
 74         pre[x]:=u;
 75         u:=x;
 76       end
 77       else begin
 78         dec(numh[h[u]]);
 79         if numh[h[u]]=0 then break;
 80         tmp:=t+1;
 81         i:=p[u];
 82         while i<>-1 do
 83         begin
 84           x:=edge[i].point;
 85           if (edge[i].flow>0) then tmp:=min(tmp,h[x]);
 86           i:=edge[i].next;
 87         end;
 88         h[u]:=tmp+1;
 89         inc(numh[h[u]]);
 90         if u<>0 then u:=pre[u];
 91       end;
 92     end;
 93   end;
 94 
 95 
 96 begin
 97   readln(m,n);
 98   fillchar(p,sizeof(p),255);
 99   len:=-1;
100   t:=n+1;
101   for i:=1 to m do
102     read(w[i]);
103   for i:=1 to n do
104   begin
105     read(y);
106     z:=0;
107     for j:=1 to y do
108     begin
109       read(x);
110       if v[x]=false then
111       begin
112         v[x]:=true;
113         z:=z+w[x];   //如果多条边连接源点和顾客，那么合并
114       end;
115       inc(s[x]);
116       a[x,s[x]]:=i;
117     end;
118     if z<>0 then
119     begin
120       add(0,i,z);
121       add(i,0,0);
122     end;
123     readln(x);
124     add(i,t,x);
125     add(t,i,0);
126   end;
127   for i:=1 to m do
128     for j:=1 to s[i]-1 do
129       for k:=j+1 to s[i] do
130       begin
131         add(a[i,j],a[i,k],inf);
132         add(a[i,k],a[i,j],0);
133       end;
134   sap;
135   writeln(ans);
136 end.

View Code