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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【网络流24题】【zkw费用流模板题】【餐巾问题napkin】  

2014-03-26 11:34:30|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    首先建图什么的不用说了吧...

    主要是用这道题整理一下zkw费用流模板。看到的一个zkw费用流是类似dinic的连续增广类型的(感觉略厉害)。所以就讲讲这一种的做法....

    首先是算法的大致流程:
    1)建图.......
    2)增广,每到达一个节点u标记该节点已经到达。然后从后继未走节点v中找d[u]+w[u,v]=d[v]的走(类似dinic连续多路增广),在查找所有邻接点的时候,用一个数目f[]记录 min(d[u]+w[u,v]-d[v])(咱可以保证没有负数233....)。如果走到汇点,就用d[v]*flow更新答案(就像dinic那样子记录个最小流量即可)然后返回。增广完进入步骤3。
    3)重标号,咱们扫描一遍所有的点,对于没有访问的节点,咱们取δ=min(f[]),如果δ未变化(即所有的slack都为本次增广前的初始值)则退出算法,否则然后把所有未访问的节点的d[]加上δ即可。然后返回步骤2。

    这里要提到几个比较好的优化( 2)中提到的连续增广实际上就是一个优化吧?),首先就是 关于 标记该节点已经到达,如果用一个bool数组然后memset或者fillchar解决的话,那么增广多次可能会有点慢,所以咱们可以使用时间戳,把每一次增广记为一个时间,然后每个点的标记就记录这个点最后一次被访问的时间,然后这样就不需要memset或者fillchar初始化了。

    然后就是松弛变量优化,其实就是那个f[]。这个类似KM算法的那个松弛。

    然后就是当前弧优化的东西,就是每一次增广假如经过同一个点多次,那么第二次就不需要经过第一次经过的那些路了(假设经过了能增广那么第一次为什么没增广?),所以记录一个s[]表示本次增广的时候应该增广的点,这个需要每一次增广的时候初始化一下,这道题每一个点连出去的除了源点之外都不多,所以就不太考虑这个优化了。

    然后就是模板了....增广挺像dinic,然后修改标号也就4,5行233....orz zkw神犇!

    然后关于此题的建图,咱是用0表示源点,然后n个点表示每一天,然后n-n'个点(n'为慢洗店洗的天数)表示的是各个洗点,最后2*n-n'+1表示源点。然后就这样了。

    代码也很短,除去建图的话压缩一下只需要40~50行不等,而且一些图zkw的效率特别高233。

    然后这道题跑了132ms,原来写的裸的spfa还差点TLE.....
    话说突然发现用 Evil君(尊称盾神?!)的代码跑此题32ms,而且代码比咱短.....= = 咱果然是蒟蒻....
==========================

program napkin;
const maxn=1010;
      maxint=100000000;

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

var e:array[0..maxn*maxn*2]of edge; {e是邻接表}
    last,d,slack:array[0..maxn*maxn]of longint; {d是标号,slack是上面说的f,即松弛变量}
    tot,n,pp,mm,ff,nn,ss,cost,time:longint;
    v:array[0..maxn*maxn]of longint;{v是记录时间戳的}

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].v:=v;e[tot].w:=w;e[tot].c:=c;
  e[tot].pre:=last[u];last[u]:=tot;
  inc(tot);e[tot].v:=u;e[tot].w:=0;e[tot].c:=-c;
  e[tot].pre:=last[v];last[v]:=tot;
end;

function dfs(p,a,t:longint):longint; {zkw的增广,类似dinic!!}
var f,flow,tmp,del:longint;
begin
  if a=0 then exit(a);
  if p=t then
   begin
     cost:=cost+a*d[t];
     exit(a);
   end;
  v[p]:=time;flow:=0;tmp:=last[p];{更新该点时间戳}
  while tmp<>-1 do
   begin
     if e[tmp].w>0 then
      begin
       del:=d[p]+e[tmp].c-d[e[tmp].v];
       slack[e[tmp].v]:=min(slack[e[tmp].v],del);{将邻接点的slack更新}
       if (del=0)and(v[e[tmp].v]<>time) then {如果满足d[u]+w[u,v]=d[v]且未访问}
         begin
           f:=dfs(e[tmp].v,min(a,e[tmp].w),t);
           if f<>0 then
             begin
              inc(flow,f);inc(e[tmp xor 1].w,f);
              dec(e[tmp].w,f);dec(a,f);
              if a=0 then break;
             end;
         end;
       end;
     tmp:=e[tmp].pre;
   end;
  exit(flow);
end;

function modify:boolean; {zkw的重标号}
var i,imp:longint;
begin
  imp:=maxint;
  for i:=0 to n shl 1-mm+1 do
   if v[i]<>time then
   begin
    imp:=min(imp,slack[i]);{求最小的slack作为δ}
    slack[i]:=maxint;{将slack初始化为∞}
   end;
  if imp=maxint then exit(true);{如果δ未更新}
  for i:=0 to n shl 1-mm+1 do
   if v[i]<>time then
    inc(d[i],imp); {将未访问的点标加上δ}
  exit(false);
end;

procedure init;
var i,j,ans:longint;
begin
  read(n,pp,mm,ff,nn,ss);
  fillchar(last,sizeof(last),255);
  fillchar(d,sizeof(d),0);
  tot:=-1;
  for i:=0 to n shl 1-mm+1 do slack[i]:=maxint;
  for i:=1 to n do
    begin
      read(j);
      addedge(0,i,maxint,pp);
      addedge(i,n shl 1-mm+1,j,0);
      if i<=n-mm then
      addedge(0,i+n,j,0);
    end;
  for i:=1 to n-mm do
   begin
     if i+mm<=n then addedge(i+n,i+mm,maxint,ff);
     if i+nn<=n then addedge(i+n,i+nn,maxint,ss);
     if i<n-mm then addedge(i+n,i+n+1,maxint,0);
   end;
  cost:=0;time:=0;
  fillchar(v,sizeof(v),0);
  repeat
    inc(time);
    v[0]:=time;
    ans:=ans+dfs(0,maxlongint,n shl 1-mm+1);
  until modify;
  write(cost);
end;

begin
  init;
end.



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

历史上的今天

评论

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

页脚

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