bzoj1391 order【网络流最小割】
题目是权限题。。。
Description
有N个工作,M种机器,每种机器你可以租或者买过来. 每个工作包括若干道工序,每道工序需要某种机器来完成,你可以通过购买或租用机器来完成。 现在给出这些参数,求最大利润
这题可以用最小割来做。
首先是建图:
对于每一个工作i,连一条s到i的边,容量为这个工作的报酬。对于每一个机器j,连一条j到t的边,容量为这个机器的价钱。再对于每一个工作i的每一个工序j,连一条i到j的边,容量为这道工序租用机器j的价钱。一开始先把所有工作的报酬加起来,最后减去最小割就是答案。
Why?
那么证明来了:
我们要将s与t分属于两个部分,在这一题建的图里有两种方法:
1、把工作对应的连到s的边割掉。
2、把工作对应的机器的边割掉或者是割掉机器连到t的边。
这也就对应了:
1、不做工作。
2、把工作的机器买下来或者是租用机器。
代码:
const maxe=3000000; maxn=5000; type edge=record x,y,next,op:longint; end; var e:array[0..maxe]of edge; a,gap,dis,pre,cur:array[0..maxn]of longint; n,m,i,j,k,s,t,u,v,cap,flow,mf,tot,p:longint; procedure adde(u,v,cap,cc:longint); begin inc(k); e[k].y:=cap; e[k].x:=v; e[k].next:=a[u]; e[k].op:=k+1; a[u]:=k; inc(k); e[k].y:=cc; e[k].x:=u; e[k].op:=k-1; e[k].next:=a[v]; a[v]:=k; end; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; procedure sap; var i,j,k,now,p,pp,dist:longint; f:boolean; begin fillchar(dis,sizeof(dis),0); fillchar(gap,sizeof(gap),0); for i:=s to t do cur[i]:=a[i]; mf:=0; now:=s; gap[t]:=t; flow:=2147483647; while dis[s]<=t do begin if now=t then begin flow:=2147483647; i:=s; while i<>t do begin flow:=min(flow,e[cur[i]].y); i:=e[cur[i]].x; end; i:=s; while i<>t do begin dec(e[cur[i]].y,flow); inc(e[e[cur[i]].op].y,flow); i:=e[cur[i]].x; end; mf:=mf+flow; now:=s; end; p:=cur[now]; f:=true; while p<>0 do begin pp:=e[p].x; if (e[p].y>0) and (dis[now]=dis[pp]+1) then begin cur[now]:=p; pre[pp]:=now; now:=pp; f:=false; break; end; p:=e[p].next; end; if f then begin dec(gap[dis[now]]); if gap[dis[now]]=0 then break; cur[now]:=a[now]; p:=a[now]; dis[now]:=t+1; while p<>0 do begin pp:=e[p].x; if (e[p].y>0) then dis[now]:=min(dis[pp]+1,dis[now]); p:=e[p].next; end; inc(gap[dis[now]]); if now<>s then now:=pre[now]; end; end; end; begin //assign(input,'1.in'); //assign(output,'2.out'); //reset(input); //rewrite(output); read(n,m); s:=0; t:=n+m+1; for i:=1 to n do begin read(cap,p); tot:=tot+cap; adde(s,i,cap,0); for j:=1 to p do begin read(u,v); adde(i,n+u,v,0); end; end; for i:=1 to m do begin read(cap); adde(n+i,t,cap,0); end; sap; writeln(tot-mf); //close(input); //close(output); end.</b>
PS:这题再一次提醒了我边的临接表要开边数的两倍。。。还有又有一个n打成m了。。。
发表回复