注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【网络流24题】【费用流】【深海机器人问题】  

2014-01-30 13:49:02|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
  题意中的限制有:
   1)深海机器人可以从多个出发点出发,然后从多个返回点回来..
    看到这个就很容易YY出这是多源多汇的问题,我们建立一个源点,然后对于每一个出发点,连一条容量为这个出发点所能出发的最多机器人数目的边,然后建立一个汇点,对于每一个回收点,连一条容量为这个回收点所能回收的机器人的最多数目,这样子机器人实际上就被看做流了...
   2)然后生物标本..毫无疑问地可以YY成费用,我们对每一个点拆点成四个,然后分成两份,两份之间连边,一个的容量为无穷大,费用为0,一个的容量为1,费用为生物标本的价值,这样子我们满足了两个条件:
   1.每一个生物标本只能被采集一次(因为那一条容量为1),用SPFA跑的时候肯定优先走这一条容量为1的。
   2.允许多个机器人在同一个点上(它们都可以走那条容量无穷大的边)
   然后就是最大费用最大流的问题...
   另外题目输入看半天没看懂....突然才发现边上才是生物标本,而不是点上。
    所以上面2)的拆点就可以不拆了( 2的拆点用于生物标本在点上吧),我们可以把每一个坐标看成一个点,对它的北方和东方的相邻点,如果路径上无标本,连一条容量无穷,费用为0的有向边即可。否则的话我们拆边,把一条边拆成两条,一条费用为0,容量无穷,一条费用为生物标本价值,容量为1,然后跑最大费用最大流即可。
  p*q的网格,实际上有 (p+1)*(q+1)个点,对于 第 (i,j)我们定义 i*(q+1)+j+1为它的编号,但是这样可能会与 一般习惯中的 0作为源点冲突,所以再加个1.一开始是读横排的,第i行的第j条边的出发点为 (i-1,j-1),读竖排的时候第i行的第J条边的出发点为 (J-1,I-1)。
  然后这样依次连边即可AC了。
==============================================

program flow20;
const maxn=300;
      maxe=5000;

type lin=record
     u,v,w,c,pre:longint;
     end;

var
  e:array[0..maxe]of lin;
  que,d,low,pre,last:array[0..maxn]of longint;
  v:array[0..maxn]of boolean;
  cost,p,q,a,b,tot:longint;

function calc(i,j:longint):longint;
begin
  exit(i*(q+1)+j+2);
end;

function min(a,b:longint):longint;
begin
  if a<b then exit(a) else exit(b);
end;

procedure addedge(u,v,w,c:longint);
begin
  inc(tot);
  e[tot].u:=u;
  e[tot].v:=v;
  e[tot].w:=w;
  e[tot].c:=c;
  e[tot].pre:=last[u];
  last[u]:=tot;
  inc(tot);
  e[tot].u:=v;
  e[tot].v:=u;
  e[tot].w:=0;
  e[tot].c:=-c;
  e[tot].pre:=last[v];
  last[v]:=tot;
end;

function spfa(s,t:longint):boolean;
var l,r,u,tmp,aug:longint;
begin
  fillchar(que,sizeof(que),0);
  fillchar(d,sizeof(d),254);
  fillchar(low,sizeof(low),0);
  fillchar(pre,sizeof(pre),0);
  fillchar(v,sizeof(v),false);
  l:=0;r:=1;que[l]:=s;
  d[s]:=0;v[s]:=true;
  low[s]:=maxlongint;
  low[t]:=low[s];
  while l<>r do
   begin
     u:=que[l];
     tmp:=last[u];
     while tmp<>-1 do
      begin
        if (d[e[tmp].v]<d[u]+e[tmp].c)and(e[tmp].w>0) then
         begin
           d[e[tmp].v]:=d[u]+e[tmp].c;
           pre[e[tmp].v]:=tmp;
           low[e[tmp].v]:=min(low[u],e[tmp].w);
           if not v[e[tmp].v] then
            begin
              que[r]:=e[tmp].v;
              r:=(r+1)mod maxn;
              v[e[tmp].v]:=true;
            end;
         end;
        tmp:=e[tmp].pre;
      end;
     v[u]:=false;
     l:=(l+1)mod maxn;
   end;
  if low[t]=maxlongint then exit(false);
  cost:=cost+d[t]*low[t];
  u:=t;aug:=low[t];
  while u<>s do
   begin
     dec(e[pre[u]].w,aug);
     inc(e[pre[u] xor 1].w,aug);
     u:=e[pre[u]].u;
   end;
  exit(true);
end;

procedure init;
var i,j,k,u,x,y,r,t:longint;
begin
  read(a,b);
  read(p,q);
  tot:=-1;
  t:=(p+1)*(q+1)+2;
  fillchar(last,sizeof(last),255);
  for i:=0 to p do
   for j:=1 to q do
    begin
      read(k);
      u:=calc(i,j-1);
      if k=0 then addedge(u,u+1,1 shl 20,0)
             else begin
                  addedge(u,u+1,1 shl 20,0);
                  addedge(u,u+1,1,k);
                  end;
    end;
  for i:=0 to q do
   for j:=1 to p do
    begin
      read(k);
      u:=calc(j-1,i);
      if k=0 then addedge(u,u+q+1,1 shl 1,0)
             else begin
                  addedge(u,u+q+1,1 shl 20,0);
                  addedge(u,u+q+1,1,k);
                  end;
    end;
  for i:=1 to a do
   begin
     read(r,x,y);
     u:=calc(x,y);
     addedge(0,u,r,0);
   end;
  for i:=1 to b do
   begin
     read(r,x,y);
     u:=calc(x,y);
     addedge(u,t,r,0);
   end;
  cost:=0;
  while spfa(0,t) do;
  writeln(cost);
end;

begin
  init;
end.



  评论这张
 
阅读(27)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018