【题意】
m个员工加工n种产品,每种产品需要c[i]个
已知m个员工各会加工什么商品
让员工加工需要一些费用,根据加工数量的不同花费也不同
0~t[i][1]加工一个需要w[i][1]的费用
t[i][1]+1~t[i][2]加工一个需要w[i][2]的费用
……
以此类推
求最小费用
【输入】
第一行m、n
接下来一行n个数字表示对n中物品的需求
之后是一个m*n的矩阵
表示员工会做哪些物品
接下来描述m个员工的加工费用
第一行s表示区间个数
第二行表示区间断点,s=0时没有
第三行表示区间费用
费用具有单调性
【输出】
最小费用
这套题里最简单的一道
比较裸的费用流
把员工拆点,用s+1条边来描述不同阶段的的费用,流量为阶段长度,然后从员工向可完成的物品上连边
物品向汇连边,流量为物品所需数量
源点向员工连边,流量无穷大
然后费用流即可
program job; const e=800; var max,tot,s,m,n,i,j,k,c:longint; last,dis,root:array [0..801] of longint; dl,point,flow,cost,next:array [0..200001] of longint; w,t:array [0..10] of longint; function anti (now:longint):longint; begin if now and 1 = 1 then exit(now+1) else exit(now-1); end; procedure connect (u,v,f,c:longint);inline; begin inc(tot); point[tot]:=v; flow[tot]:=f; cost[tot]:=c; next[tot]:=root[u]; root[u]:=tot; end; function mcmf:int64; var ans:int64; begin ans:=0; repeat fillchar(dis,sizeof(dis),63); tot:=0; i:=0; dl[0]:=0; dis[0]:=0; while i<=tot do begin k:=root[dl[i]]; while k<>0 do begin if (flow[k]>0)and(dis[point[k]]>dis[dl[i]]+cost[k]) then begin inc(tot); dl[tot]:=point[k]; dis[point[k]]:=dis[dl[i]]+cost[k]; last[point[k]]:=k; end; k:=next[k]; end; inc(i); end; if dis[e]=dis[801] then break; i:=e; max:=maxlongint; while i<>0 do begin if flow[last[i]]<max then max:=flow[last[i]]; i:=point[anti(last[i])]; end; ans:=ans+int64(dis[e])*max; i:=e; while i<>0 do begin flow[last[i]]:=flow[last[i]]-max; flow[anti(last[i])]:=flow[anti(last[i])]+max; i:=point[anti(last[i])]; end; until false; exit(ans); end; begin assign(input,'job.in'); reset(input); assign(output,'job.out'); rewrite(output); read(m,n); for i:=1 to n do begin read(c); connect(2*m+i,e,c,0); connect(e,2*m+i,0,0); end; for i:=1 to m do for j:=1 to n do begin read(c); if c=1 then begin connect(2*i,2*m+j,maxlongint div 10,0); connect(2*m+j,2*i,0,0); end; end; for i:=1 to m do begin connect(0,2*i-1,maxlongint div 10,0); connect(2*i-1,0,0,0); read(s); for j:=1 to s do read(t[j]); t[s+1]:=maxlongint div 10; for j:=1 to s+1 do begin read(w[j]); connect(2*i-1,2*i,t[j]-t[j-1],w[j]); connect(2*i,2*i-1,0,-w[j]); end; end; writeln(mcmf); close(input); close(output); end.