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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【算法】【zkw费用流】  

2014-03-25 22:56:30|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    剩余时间就用来研究下zkw费用流的原理以及它的写法....
    一般说为什么要学zkw费用流而不用spfa,往往幕后音都是“咱一直用spfa费用流的,直到有一天...233”。
    然后看到一句话 “增广的时候像sap,修改标号的时候像KM...”果断默默地去复习了下sap和km233....
    先上zkw费用流网上的代码:代码君 ,p和c++都有,造福人类。
    然后就是Zkw费用流的思想。
    首先有一个数组叫dist[],表示的就是 汇点T到每一个点的最短路的估计,然后这个一开始初始化的时候可以直接变成0,或者从T BFS一遍得到。类似最短路,在每一次费用流求完SPFA之后显然这个有性质 dist[u]<=dist[v]+w[v,u],然后对于最短路上就有dist[u]=dist[v]+w[v,u]。
    然后咱们来复习一下KM算法到底是怎么做的咩....
    KM算法相当于一种贪心吧,每一次只加入原图中的大的边权,然后用匈牙利求最大权匹配,如果匹配上的话,那么显然这个时候的就是最大权匹配了(因为咱都是一直用的最大的边来匹配的),如果不行的话就再加入一条第二大的边权求匹配,然后就是这样,至于加边的方法,实现起来就是那个点的顶标d[]。也就是说只有顶标d[u]+d[v]=w[u,v]的边w[u,v]才能够被加入进去求最大权匹配。而一般的都满足 d[u]+d[v]<=w[u,v]。
    回头看看咱们的式子 dist[u]<=dist[v]+w[v,u],咱们可以模仿KM的做法,每一次都只沿着dist[u]=dist[v]+w[v,u]的方向增广,然后关于不能增广了呢?得修改dist[]!,类比KM,给所有增广路上的点u的dist加上一个w,w=min(dist[v]+w[v,u]-dist[u]),v为和u相连的点。然后再增广即可。
    上面是个人的口胡...不知道理解的对不对....
    然后大概就这样了,待最近时间写个模板出来。
    以下是代码
   ===========================


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

var e:array[0..maxn*maxn*2]of edge;
    last,d,slack:array[0..maxn*maxn]of longint;
    cost,time:longint;
    v:array[0..maxn*maxn]of longint;

function dfs(p,a,t:longint):longint;
var f,flow,tmp,del,next: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];
       if slack[e[tmp].v]>del then slack[e[tmp].v]:=del;
       if (del=0)and(v[e[tmp].v]<>time) then
         begin
           if a<e[tmp].w then next:=a else next:=e[tmp].w;
           f:=dfs(e[tmp].v,next,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;
var i,imp:longint;
begin
  imp:=maxint;
  for i:=0 to n shl 1-mm+1 do
   if v[i]<>time then
   begin
    if imp>slack[i] then imp:=slack[i];
    slack[i]:=maxint;
   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;

然后就是 主过程:

 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;

求出来的ans就是最大流,然后cost就是最小费用。

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

历史上的今天

评论

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

页脚

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