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

poj3469 Dual Core CPU【网络流最小割】

  • 内容
  • 评论
  • 相关

http://poj.org/problem?id=3469
大意就是有n个程序，有两个CPU，每个程序在不同的CPU上运行花费不同，然后有m对程序是要共享数据的，如果不在同一个CPU上运行就要有额外的花费，输出最小的花费。

一个最小割的题目。
建图：每个程序i建一个点，连一条s到i的边，容量为程序i在第一个CPU上运行的花费，再连一条i到t的边，容量为程序i在第二个CPU上运行的花费。最后对每一对程序i和j连一条i到j的边，容量为不在同一个CPU上运行的花费。

为啥这样是对的？下面是证明：
如果点i分到s割，那么必定割去i到t的边，也就意味着程序i在第二个CPU上运行，同理如果点i分到t割，说明i在第一个CPU上运行。而对于每对程序i和j，如果它们一个分到s割一个分到t割，就要割去连接着它们的边，就相当于付出额外的花费。

代码：

const
  maxe=500000;
  maxn=20005;
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: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>t do
      begin
        flow:=min(flow,e[cur[i]].y);
        i:=e[cur[i]].x;
      end;
      i:=s;
      while i&lt;&gt;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&lt;&gt;0 do
    begin
      pp:=e[p].x;
      if (e[p].y&gt;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&lt;&gt;0 do
      begin
        pp:=e[p].x;
        if (e[p].y&gt;0) then dis[now]:=min(dis[pp]+1,dis[now]);
        p:=e[p].next;
      end;
      inc(gap[dis[now]]);
      if now&lt;&gt;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+1;
  for i:=1 to n do
  begin
    read(u,v);
    adde(s,i,u,0);
    adde(i,t,v,0);
  end;
  for i:=1 to m do
  begin
    read(u,v,cap);
    adde(u,v,cap,cap);
  end;
  sap;
  writeln(mf);
 // close(input);
 // close(output);
end.</b>

评论

0条评论

发表回复

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.