1. 首页
  2. Let's OI!
  3. 正文

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了。。。

评论

0条评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。