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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【网络流24题】【分层图最小费用最大流】【餐巾计划问题】  

2014-01-27 17:52:11|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    这一题的网络流模型现在还是感觉挺神的,一开始建了一个自以为很神奇的图..结果就被大神给虐了...
    【网络流24题】【餐巾计划问题】 - z55250825 - z55250825【左边的图假设快洗店两天洗完,慢洗店三天】
  然后费用在相应的道路上,实际上那时咱是在完全没有理解网络流的情况下YY的图...
  这一个图不能表示每一天需要的餐巾一定会满,然后也不能够表示哪一些餐巾被送到下一天用。所以显然是错的。
  然后我们来看看如何构图来满足条件。首先是要求保证每一天都要有那么多的餐巾来供应。这一点我们可以把每一天拆成一个点,然后将它们分别向汇点连一条容量为当天需求餐巾量的边。这样子,只要我们保证流入每一天的点的流足够多,那么在求最大流之后它们显然可以满足每一条边都流了容量大小的流,即供应了容量大小的餐巾,这里我们可以把餐巾看做流。
  然后我们要供应餐巾,我们从汇点连一条无穷大的边到每一个点即可,但是这条路得有费用,费用即买一条餐巾的钱。
  然后建好的图如下,这个图跑出来的方案显然就是只购买餐巾,当天用完的餐巾就扔掉。
  【网络流24题】【餐巾计划问题】 - z55250825 - z55250825
  然后我们还要考虑其他的条件。首先就是快洗店和慢洗店....
  快洗店的作用就是给把某一天的流过去的再流到其他的点里面,需要费用为快洗店的每块费用,所以我们可以建立一个节点表示当天的各种洗点(快洗店和慢洗店最好用一个点表示,这样子我们从源点连一条容量为当天所需餐巾量的边,这样就可以限制流入这个点的餐巾量小于当天消耗的),然后把它与源点连一条边,容量为当天所需餐巾量,费用为0,然后我们洗好了之后就需要把流送到其他天去,我们假设快餐店洗的天数为J,对于第I天的洗店点,我们将它与第I+J天连一条容量为无穷大,费用为快洗店价格的边,然后慢洗店同理,这样子我们就解决了快洗店慢洗店的问题。
   还有一个问题就是有一些餐巾需要流到下一天或者下下天再送到洗店去洗,这个其实也很简单,首先它保存下来了说明它就流向了洗点,但是它又不能从当天的洗点流出来,所以我们在每一个第 i 天和第 i+1天的洗店点间连一条费用为0,容量无穷大的边即可。
  然后把上面的图跑最小费用最大流即可。建好的图应该如下所示:
 【网络流24题】【餐巾计划问题】 - z55250825 - z55250825
   上面假设快洗店2天洗完,慢洗店三天洗完...
   然后就可以AC了...
   这次又是第一次写最小费用最大流,一般的都是写SPFA增广的,注意由于Dijkstra不能处理负环所以在这里是用不上的。
   然后就是如何使用SPFA增广。找最小费用的最短路,我们可能会纠结的就是关于不知道流量的问题,但是流过一条路的流量实际上是固定的,所以我们只需要考虑费用就可以了。也就是说每一次只需要找单位流量费用和最少的路径即可。这个SPFA可以做。往回扩展的时候,记录一个PRE,表示这个点是由哪个点松弛过来的,记录一个LOW,表示从源点沿某条路到这个点的最小容量。然后就可以了。对于建图,我们令 0,1表示的是源点和汇点,然后对于第i天,为 i shl 1 和 i shl 1 xor 1即可。
 这里傻×的很久没写SPFA了,把 表示某个点是否在队列中 加入了判断是否松弛中,WA了半天。实际上只要可以松弛就松弛,然后松弛完用这个判断是否该把松弛的点加入队列中。
下面的代码仅是实现上面的构图,并未优化,跑第六个点的时候就够呛了....优化
可以加邻接表而不是邻接矩阵,另外还有就是SPFA的优化,24题的本质在于构图,
模板优化以后有的是时间

ps:已经有了优化的代码了,不过是zkw费用流的,跑完所有数据132ms,还可以去掉一些函数来加速,代码在这儿:
============================================================

program napkin;
const maxn=1500;
      oo=16843009;

var c,g:array[0..maxn,0..maxn]of longint;
    que,d,pre,low:array[0..maxn]of longint;
    v:array[0..maxn]of boolean;
    max,mcost,n,p,m,f,t,s:longint;

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

function spfa(s,t:longint):boolean;{spfa部分}
var i,u,l,r,aug,tmp:longint;
begin
  fillchar(que,sizeof(que),0);
  fillchar(d,sizeof(d),1); {初始化为无限大,就是开头定义的oo,oo数值可以自己写个程序得到}
  fillchar(v,sizeof(v),false);
  fillchar(pre,sizeof(pre),0);
  fillchar(low,sizeof(low),1);
  l:=0;r:=1;que[l]:=s;
  d[s]:=0;v[s]:=true;
  while l<>r do
    begin
      u:=que[l];
      for i:=0 to n shl 1 xor 1 do
        if (g[u][i]>0)and(d[i]>d[u]+c[u][i])then
          begin
            pre[i]:=u;
            low[i]:=min(low[u],g[u][i]);
            d[i]:=d[u]+c[u][i];
            if not v[i] then
             begin
               que[r]:=i;
               r:=(r+1)mod maxn;
               v[i]:=true;
             end;
          end;
      v[u]:=false;
      l:=(l+1)mod maxn;
    end;
  if low[t]=oo then exit(false);
  u:=t;aug:=low[t];{沿着SPFA出来的增广路增广的过程}
  max:=max+aug;
  mcost:=mcost+low[t]*d[t];
  while u<>s do
   begin
     tmp:=u;
     u:=pre[u];
     dec(g[u][tmp],aug);
     inc(g[tmp][u],aug);
   end;
  exit(true);
end;

procedure init;
var i,j:longint;
begin
  fillchar(g,sizeof(g),255);
  fillchar(c,sizeof(c),0);
  read(n,p,m,f,t,s);
  for i:=1 to n do {构图}
   begin
     read(j);
     g[0][i shl 1]:=oo;
     g[i shl 1][0]:=0;
     c[0][i shl 1]:=p;
     c[i shl 1][0]:=-p;
     g[0][i shl 1 xor 1]:=j;
     g[i shl 1 xor 1][0]:=0;
     g[i shl 1][1]:=j;
     g[1][i shl 1]:=0;
     if i<>1 then
      begin
       g[(i-1)shl 1 xor 1][i shl 1 xor 1]:=oo;
       g[i shl 1 xor 1][(i-1)shl 1 xor 1]:=0;
      end;
     if i+m<=n then
      begin
       g[i shl 1 xor 1][(i+m)shl 1]:=maxlongint;
       g[(i+m)shl 1][i shl 1 xor 1]:=0;
       c[i shl 1 xor 1][(i+m)shl 1]:=f;
       c[(i+m)shl 1][i shl 1 xor 1]:=-f;
      end;
     if i+t<=n then
      begin
       g[i shl 1 xor 1][(i+t)shl 1]:=maxlongint;
       g[(i+t)shl 1][i shl 1 xor 1]:=0;
       c[i shl 1 xor 1][(i+t)shl 1]:=s;
       c[(i+t)shl 1][i shl 1 xor 1]:=-s;
      end;
   end;
  max:=0; {max为最大流,这道题木有太大作用,可判断是否有可行方案}
  mcost:=0;{最小费用}
  while spfa(0,1) do;{最小费用最大流}
  writeln(mcost);
end;

begin
  init;
end.


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

历史上的今天

评论

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

页脚

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