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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【网络流24题】【分层图最短路】【汽车加油行驶问题】  

2014-01-29 10:24:08|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   又是一道不知道如何构图的题目....
   我们可以YY一下,首先关于加油站费用,我们可以经过把一个点拆成两个点,中间连一条容量为1的边,费用为A,然后就是建加油站,我们可以把每一个空地的点,拆成四个点,两两相连,其中一个代表建加油站的费用C+A,另一个就是路过,无费用,然后对于X,Y坐标减少,我们也可以连一条费用为B的边即可。但是...咱们还不能表示汽车最多行驶K...所以之前的YY也是没有意义的...
    然后看到了题解...跟星际实际上是一样的,需要建立K层图才行....
    将这个图拆成K层相同的图,每一层的每一个顶点,对应原图的相应顶点,只是油量由1~K不等。
    然后我们在新的图上考虑...对于新图上的 点 (i,j,l)(i,j表示坐标,l表示油量),如果原图i,j是加油站,而l<>k(即油量未满)那么咱们得将 (i,j,l)与(i,j,k)连一条边,权值为A,否则按普通点处理。然后如果原图 i,j为空地,油量未满,我们也可以建立一个加油站,即 将 (i,j,l)与(i,j,k)连边,边权为 A+C,油量慢的话就不用建了。然后假设我们不加油,那么 我们给 (i,j,k) 与 (i+1,j,k-1)和 (i,j+1,k-1)连一条边权为0的边,然后把 (i-1,j,k-1)和(i,j-1,k-1)连一条边权为B的边,然后这样建好图之后跑最短路即可(网络流都不要了!),然后对于跑出来的结果,就是 min(d(n,n,p))(1<=p<=k)
    上面的模型真是太精妙了咩...
     写了一个模拟链表优化的邻接表,然后跑SPFA即可。(堆加dijkstra改天写一个)
     至于拆点,我们对于第p层的 i,j个点可以拆为 (p-1)*n*n+(i-1)*n+j 。实际上就是类似N进制的东西...
     注意上面连的全部都是有向边。
     又一次傻×的忘记了SPFA最后找完u的所有邻接边之后要把它的 v[](表示是否在队列中)改为 false,Wa了半天...
=====================================================================

program flow15;
const maxn=700000;
type
   lin=record
   v,w,pre:longint;
   end;

var g:array[1..100,1..100]of longint;
    n,max,a,b,c,tot:longint;
    e:array[1..maxn]of lin;
    last,d:array[1..maxn div 5]of longint;
    que:array[0..maxn]of longint;
    v:array[0..maxn div 5]of boolean;

function calc(i,j,p:longint):longint;{计算(i,j)油量为k的点的编号}
begin
  exit(p*n*n+(i-1)*n+j);
end;

procedure addedge(u,v,w:longint); {给邻接表加边}
begin
  inc(tot);
  e[tot].v:=v;
  e[tot].w:=w;
  e[tot].pre:=last[u];
  last[u]:=tot;
end;

procedure spfa(s:longint); {Spfa求最短路}
var tmp,u,l,r:longint;
begin
  fillchar(que,sizeof(que),0);
  fillchar(d,sizeof(d),1);
  fillchar(v,sizeof(v),false);
  l:=0;r:=1;que[l]:=s;
  d[s]:=0;v[s]:=true;
  while l<>r do
   begin
     u:=que[l];
     tmp:=last[u];
     while tmp<>0 do
      begin
        if d[e[tmp].v]>d[u]+e[tmp].w then
         begin
           d[e[tmp].v]:=d[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;
end;

function min(a,b:longint):longint;{不解释...}
begin
  if a<b then exit(a) else exit(b);
end;

procedure init;
var i,j,k,u,v,ans:longint;
begin
  read(n,max,a,b,c);
  fillchar(last,sizeof(last),0);
  tot:=0;
  for i:=1 to n do
    for j:=1 to n do
      read(g[i][j]);
  for i:=1 to n do
   for j:=1 to n do
    for k:=0 to max do {枚举分层图的每一个节点,然后分类讨论并加边}
     begin
       if (g[i][j]=1)and(k<>max)then {当前地区有油库且油量未满{必须加油}}
        begin
          u:=calc(i,j,k);
          v:=calc(i,j,max);
          addedge(u,v,a);
        end;
       if (g[i][j]=0)and(k<>max)then {当前地区无油库且油量未满{可以修一个油库并加油}}
        begin
          u:=calc(i,j,k);
          v:=calc(i,j,max);
          addedge(u,v,a+c);
        end;
       if (k<>0)and(g[i][j]=0)then {当前地区无油库,考虑向周围走}
        begin
          u:=calc(i,j,k);
          if i<n then begin
          v:=calc(i+1,j,k-1);
          addedge(u,v,0);
          end;
          if j<n then begin
          v:=calc(i,j+1,k-1);
          addedge(u,v,0);
          end;
          if i>1 then begin
          v:=calc(i-1,j,k-1);
          addedge(u,v,b);
          end;
          if j>1 then begin
          v:=calc(i,j-1,k-1);
          addedge(u,v,b);
          end;
        end;
       if (k=max)and(g[i][j]=1)then {当前地区有油库,且油量已满,不需要加油,考虑向四周走}
        begin
          u:=calc(i,j,k);
          if i<n then begin
          v:=calc(i+1,j,k-1);
          addedge(u,v,0);
          end;
          if j<n then begin
          v:=calc(i,j+1,k-1);
          addedge(u,v,0);
          end;
          if i>1 then begin
          v:=calc(i-1,j,k-1);
          addedge(u,v,b);
          end;
          if j>1 then begin
          v:=calc(i,j-1,k-1);
          addedge(u,v,b);
          end;
        end;
     end;
  spfa(calc(1,1,max)); {跑SPFA}
  ans:=maxlongint;
  for i:=0 to max do
   ans:=min(ans,d[calc(n,n,i)]);
  write(ans);
end;

begin
  assign(input,'f.in');reset(input);
  init;
  close(input);
end.

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

历史上的今天

评论

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

页脚

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