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

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

最小费用最大流模板、算法  

2014-03-19 23:07:35|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

(整篇文章属个人理解)-------------(未经本人允许不准转载)

之所以这么称呼 ,是因为你要让整张图流过的流量达到最大(必须这么做),而在这个条件下你可以用算法来使整张图的费用最少。而这个算法便是最小费用最大流算法

 

 而我们来介绍这个算法:此算法其实是个贪心,每次做找到从起点到终点的最短路径,(可以把费用看成距离),而这个路径一定是答案的一部分,这里说的一部分便不一定是真正解的路径,只能保证答案是正确的,若不能理解,你可以想想NlogN逆序对的算法(也是长度最优,而数组里组成的不一定是最优),比较类似的。而为什么这种算法正确的,因为第一次可能我们确定的路径是错的,而第二次可以用第一次做的反向边来更新最优值。怎么说呢?看下图:

最小费用最大流模板、算法 - 山哥 - OI之路,漫漫人生
 

设黑色点为起点,深蓝色点为终点,每条边的容量为1。首先假设黑-绿-浅蓝-深蓝是一条最短路,那如果没有逆边,则下次黑色到红色再到蓝色就没有边了,因为浅蓝到深蓝的容量已经被上次减掉了。  而如果有了逆边,则红色会到蓝色,蓝色又会到绿色(蓝绿之间有逆边),从而绿-褐色-深蓝。明显可能最优解是:黑-绿-褐色-深蓝和黑--浅蓝-深蓝。   这也是最大流算法中的核心思想。两者在此处类似。

 算法具体实现:

最小费用路算法的复杂度主要依靠于求最短路的方法,由于负权的存在,不会选择dijstra等算法,一般bellman-ford,spfa等用来解决费用流的最短路问题。

1.初始没有流。 2.在残流网络中从源点到汇点找一条到最小费用路,若不存在则结束。3.沿步骤2找到的最小费用路记录答案、增减容量。转步骤0。

推荐用边表+SPFA来解决此类问题。(边表可以解决两个点之间有多条重边的情况)

 代码模板:

#include<cstdio>

#include<cstring>

#define maxn //队列queue要开大哦,我大概开4*N;

#define maxm //边表一般开5*N,4种方向的边

#define maxx 

using namespace std;

int x,y,c,i,j,n,m,h,t,tot,k,ans;

int fa[maxn],queue[maxn],pre[maxn],dis[maxn];

bool vis[maxn];

struct node{int start,next,end,cost,f;

}g[maxm*5];

void add(int a,int b,int v)

 {g[tot].end=b;g[tot].start=a;g[tot].cost=v;

  g[tot].next=fa[a];fa[a]=tot;

  g[tot].f=1;tot++;

  g[tot].end=a;g[tot].start=b;g[tot].cost=-v;

  g[tot].next=fa[b];g[tot].f=0;fa[b]=tot;

  tot++;

 }

void spfa()

 {

 int i,w,h,t;

 初始化

 queue[1]=1;vis[1]=true;

 h=0;t=1;dis[1]=0;

 while (h<=t) {

             w=queue[++h];

             for (i=fa[w];i!=-1;i=g[i].next)

             if ((dis[g[i].end]>dis[w]+g[i].cost)&&g[i].f)

                   {

                   dis[g[i].end]=dis[w]+g[i].cost;

                   pre[g[i].end]=i;

                   if (!vis[g[i].end]){

                                      vis[g[i].end]=true; 

                                      queue[++t]=g[i].end; 

                                       } 

                   }

             vis[w]=false;

             }

 }

int main()

{

 边表读入。。。

while (1){

spfa();

    if  (dis[n]==maxx) break;

    tem=maxx;

 for (i=pre[n];i!=-1;i=pre[g[i].start])

   

    tem=min(g[i].f,tem);//找到这条路径的流量。

for (i=pre[n];i!=-1;i=pre[g[i].start])

          {g[i].f+=tem;g[i^1]-=tem;}增加逆边和增减容量;xor是i的逆边;

    IN_C(答案记录)

(ans+=单位流量cost*整条路径流量最小值(即这条路径的流量tem);

 

                  }

printf("%d\n",ans);

return 0;

}


  评论这张
 
阅读(20945)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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