因为题目太长懒得看，所以现在才做这道题。
每加工一个零件就花费固定的费用，一看就是费用流。
建立S，T。 S向每个人连边，每一段怒气连一条流量为这一段零件数的边。 如果i可以加工j，add(i,j,inf,0)。每种零件向T连流量为个数的边。
zkw或spfa费用流都行。
因为w是递增的所以才能这么建边。
| RunID | User | Problem | Result | Memory | Time | Language | Code_Length | Submit_Time |
| 408065 | lbz007 | 2245 | Accepted | 43300 kb | 3188 ms | Pascal/Edit | 2434 B | 2013-05-08 17:19:07 |
View Code
1 const inf=1000000000; 2 var 3 dis,tx,other,a,pre,next,head,e,x,long,w:array[0..500100]of int64; 4 v:Array[0..100010]of boolean; 5 can,kk,xx,tt,ee,ss,i,j,n,m:longint; 6 sum,ans,mincost:int64; 7 function min(aa,bb:longint):longint; 8 begin if aa>bb then exit(bb) else exit(aa); end; 9 procedure add(u,v,c,cc:longint); 10 begin 11 inc(ee);x[ee]:=u;e[ee]:=v;long[ee]:=c;w[ee]:=cc;other[ee]:=ee+1; 12 next[ee]:=head[u];head[u]:=ee; 13 inc(ee);x[ee]:=v;e[ee]:=u;long[ee]:=0;w[ee]:=-cc;other[ee]:=ee-1; 14 next[ee]:=head[v];head[v]:=ee; 15 end; 16 function spfa :boolean; 17 var i,h,t,j:longint; 18 begin 19 h:=1;t:=1; 20 for i:=ss to tt do dis[i]:=inf; 21 a[1]:=ss; pre[ss]:=-1; 22 v[ss]:=true; dis[ss]:=0; 23 while h<=t do 24 begin 25 j:=head[a[h]]; 26 while j<>0 do 27 begin 28 if (long[j]>0)and(dis[a[h]]+w[j]<dis[e[j]]) then 29 begin 30 dis[e[j]]:=dis[a[h]]+w[j]; 31 pre[e[j]]:=j; 32 if not v[e[j]] then 33 begin v[e[j]]:=true; inc(t) ;a[t]:=e[j]; end; 34 end; 35 j:=next[j]; 36 end; 37 v[a[h]]:=false; inc(h); 38 end; 39 if dis[tt]>=inf-1000 then exit(false) 40 else exit(true); 41 end; 42 procedure work; 43 var zh,flow:longint; 44 begin 45 ans:=0; mincost:=0; 46 while spfa do 47 begin 48 zh:=tt; flow:=maxlongint; 49 while pre[zh]<>-1 do 50 begin 51 flow:=min(flow,long[pre[zh]]); 52 zh:=x[pre[zh]]; 53 end; 54 ans:=ans+flow; 55 mincost:=mincost+dis[tt]*flow; 56 zh:=tt; 57 while pre[zh]<>-1 do 58 begin 59 dec(long[pre[zh]],flow); 60 inc(long[other[pre[zh]]],flow); 61 zh:=x[pre[zh]]; 62 end; 63 end; 64 end; 65 66 begin 67 readln(n,m); 68 tt:=n+m+1;ss:=0; 69 for i:=1 to m do 70 begin 71 read(xx);sum:=sum+xx; 72 add(n+i,tt,xx,0); 73 end; 74 for i:=1 to n do 75 begin 76 for j:=1 to m do 77 begin 78 read(can); 79 if can=1 then 80 add(i,n+j,inf,0); 81 end; 82 readln; 83 end; 84 for i:=1 to n do 85 begin 86 readln(kk); 87 for j:=1 to kk do 88 read(tx[j]); 89 tx[kk+1]:=sum; 90 for j:=1 to kk+1 do 91 begin 92 read(xx); 93 add(ss,i,tx[j]-tx[j-1],xx); 94 end; 95 end; 96 work; 97 writeln(mincost); 98 end.