最小费用最大流算法

//此算法必须指定要求的最大流stream,如果结果无限循环的出现

//一些字或者什么也不出现，则说明该图达不到此流量。

#include "iostream.h"

#define max 10000

#define n 5 //根据不同问题可修改大小

#define stream 10 //根据不同问题可修改

//最大容量矩阵

int

c[n][n]={{0,10,8,max,max},{max,0,max,2,7},{max,5,0,10,max},{max,max,max,0,4},{max,max,max,max,0}};

//实际流量矩阵

int

flow[n][n]={{0,0,0,max,max},{max,0,max,0,0},{max,0,0,0,max},{max,max,max,0,0},{max,max,max,max,0}};

//费用矩阵

int

money[n][n]={{0,4,1,max,max},{max,0,max,6,1},{max,2,0,3,max},{max,max,max,0,2},{max,max,max,max,0}};

//增广链向量

int p[n]={0,0,0,0,0}; //原点到各点的最短路径

int D[n]; //原点到各点的路长(用于Dijkstra法中)

int pt[n]={0,0,0,0,0}; //原点到各点的路长(用于逐次逼近法中)

int maxflow; //设置最大流量

//----------------------------计算Vs--Vt最短路径模块---------------------------------------------//

void Dijkstra() //求源点V0到其余顶点的最短路径及其长度;得到一条增广链 {

int s[n]; //D[n]最后保存各点的最短路径长度

int i,j,k,vl,pre;

int min;

int inf=20000;

vl=0; //求V0到Vn的增广链

for(i=0;i

{

D[i]=money[vl][i]; //置初始距离值

if((D[i]!=max) && (D[i]!=0)) p[i]=1;

else p[i]=0;

}

for(i=0;i

s[vl]=1; D[vl]=0;

for(i=0;i

{

min=inf;

for(j=0;j

if((!s[j]) && (D[j]

{

min=D[j];

k=j;

}

s[k]=1;

if(min==max) break;

for(j=0;j

if((!s[j]) && (D[j]>D[k]+money[k][j]))

{

D[j]=D[k]+money[k][j];

p[j]=k+1;

}

} //此时所有顶点都已扩充到红点集S中

cout

for(i=0;i

{

if(i=n-1){

cout

pre=p[i];

while (pre!=0)

{

cout

pre=p[pre-1]; //p[]中保存的路径的顶点标号从1开始，不是0；

}

cout

}

}

//-----------------------------------END Dijkstra()-----------------------------------------//

//------------------用最大流算法的方法调整实际流量矩阵flow[][]，以扩充其流量----------------// void modify()

{

int i,min;

int pre;

if(D[n-1]==max)

{

cout

return;

}

pre=p[n-1];

i=n-1;

min=c[pre-1][i]-flow[pre-1][i]; //增广路上的最后一条边的长

while(pre!=0) //再增广路上算出所能增加流量的最大值 {

i=pre-1;

pre=p[pre-1];

if(min>c[pre-1][i]-flow[pre-1][i])

min=c[pre-1][i]-flow[pre-1][i];

if(pre==1)

pre=0;

}

if((min+maxflow)>stream)

min=stream-maxflow;

pre=p[n-1]; //在增广链上添加流量

i=n-1;

flow[pre-1][i]+=min;

while(pre!=0)

{

i=pre-1;

pre=p[pre-1];

flow[pre-1][i]+=min;

if(pre==1)

pre=0;

}

}

//----------------------------------END modify()----------------------------------//

//--------------------------------调整费用矩阵money[][]-----------------------------// void modifymoney()

{

int i,j;

int moneypre[n][n];

for(i=0;i

for(j=0;j

moneypre[i][j]=money[i][j];

for(i=0;i

for(j=0;j

{

if(i

if(c[i][j]!=max && c[i][j]>flow[i][j])

money[i][j]=moneypre[i][j];

if((c[i][j]!=max && c[i][j]==flow[i][j]) || (c[i][j]==max && flow[i][j]==max)) money[i][j]=max;}

if(i>j){

if( flow[j][i]>0 )

money[i][j]=-moneypre[j][i];

if(flow[j][i]==0)

money[i][j]=max;}

}

for(i=0;i

for(j=0;j

{

if(i==j)

money[i][j]=0;

if(money[i][j]==-max)

money[i][j]=max;

}

}

//----------------------------------END modifymoney()----------------------------------//

//----------------------------采用逐次逼近法得到一条增广链----------------------------// void approach()

{

int pf[n],ptf[n]={0,0,0,0,0}; //当N变动时，0的个数应与N一致

int min=max;

int i,j,flag;

for(j=0;j

pt[j]=money[0][j]; //直接距离做初始解

do{

flag=1;

for(j=0;j

pf[j]=pt[j]; //将上一次得到的路径迭代结果保存入pf[]

for(i=0;i

{

min=pt[i];

for(j=0;j

{

if(min>(pt[j]+money[j][i]))

min=pt[j]+money[j][i];

}

ptf[i]=min;

}

for(i=0;i

{

pt[i]=ptf[i];

if(pf[i]!=pt[i])

flag=0; //两次迭代的值不同,继续

}

}while(flag==0);

j=n-1;

for(i=0;i

if(pt[i]+money[i][j]==pt[j])

{

p[j]=i+1; //p[j]中的下标从1开始

if(p[j]==1) break;

j=i;

i=-1;

}

for(i=0;i

D[i]=pt[i];

}

//------------------------------END approach()------------------------------//

void main()

{

int i,j;

Dijkstra();

while( 1 )

{

modify(); //调整流量矩阵

maxflow=0;

for(j=0;j

{

if(flow[0][j]!=max)

maxflow+=flow[0][j];

}

if(maxflow==stream) break;

modifymoney();

approach(); //采用逐次逼近法得到一条增广链

}

cout

for(i=0;i

{

for(j=0;j

cout

cout

}

cout

for(i=0;i

{

for(j=0;j

cout

}

//此算法必须指定要求的最大流stream,如果结果无限循环的出现

//一些字或者什么也不出现，则说明该图达不到此流量。

#include "iostream.h"

#define max 10000

#define n 5 //根据不同问题可修改大小

#define stream 10 //根据不同问题可修改

//最大容量矩阵

int

c[n][n]={{0,10,8,max,max},{max,0,max,2,7},{max,5,0,10,max},{max,max,max,0,4},{max,max,max,max,0}};

//实际流量矩阵

int

flow[n][n]={{0,0,0,max,max},{max,0,max,0,0},{max,0,0,0,max},{max,max,max,0,0},{max,max,max,max,0}};

//费用矩阵

int

money[n][n]={{0,4,1,max,max},{max,0,max,6,1},{max,2,0,3,max},{max,max,max,0,2},{max,max,max,max,0}};

//增广链向量

int p[n]={0,0,0,0,0}; //原点到各点的最短路径

int D[n]; //原点到各点的路长(用于Dijkstra法中)

int pt[n]={0,0,0,0,0}; //原点到各点的路长(用于逐次逼近法中)

int maxflow; //设置最大流量

//----------------------------计算Vs--Vt最短路径模块---------------------------------------------//

void Dijkstra() //求源点V0到其余顶点的最短路径及其长度;得到一条增广链 {

int s[n]; //D[n]最后保存各点的最短路径长度

int i,j,k,vl,pre;

int min;

int inf=20000;

vl=0; //求V0到Vn的增广链

for(i=0;i

{

D[i]=money[vl][i]; //置初始距离值

if((D[i]!=max) && (D[i]!=0)) p[i]=1;

else p[i]=0;

}

for(i=0;i

s[vl]=1; D[vl]=0;

for(i=0;i

{

min=inf;

for(j=0;j

if((!s[j]) && (D[j]

{

min=D[j];

k=j;

}

s[k]=1;

if(min==max) break;

for(j=0;j

if((!s[j]) && (D[j]>D[k]+money[k][j]))

{

D[j]=D[k]+money[k][j];

p[j]=k+1;

}

} //此时所有顶点都已扩充到红点集S中

cout

for(i=0;i

{

if(i=n-1){

cout

pre=p[i];

while (pre!=0)

{

cout

pre=p[pre-1]; //p[]中保存的路径的顶点标号从1开始，不是0；

}

cout

}

}

//-----------------------------------END Dijkstra()-----------------------------------------//

//------------------用最大流算法的方法调整实际流量矩阵flow[][]，以扩充其流量----------------// void modify()

{

int i,min;

int pre;

if(D[n-1]==max)

{

cout

return;

}

pre=p[n-1];

i=n-1;

min=c[pre-1][i]-flow[pre-1][i]; //增广路上的最后一条边的长

while(pre!=0) //再增广路上算出所能增加流量的最大值 {

i=pre-1;

pre=p[pre-1];

if(min>c[pre-1][i]-flow[pre-1][i])

min=c[pre-1][i]-flow[pre-1][i];

if(pre==1)

pre=0;

}

if((min+maxflow)>stream)

min=stream-maxflow;

pre=p[n-1]; //在增广链上添加流量

i=n-1;

flow[pre-1][i]+=min;

while(pre!=0)

{

i=pre-1;

pre=p[pre-1];

flow[pre-1][i]+=min;

if(pre==1)

pre=0;

}

}

//----------------------------------END modify()----------------------------------//

//--------------------------------调整费用矩阵money[][]-----------------------------// void modifymoney()

{

int i,j;

int moneypre[n][n];

for(i=0;i

for(j=0;j

moneypre[i][j]=money[i][j];

for(i=0;i

for(j=0;j

{

if(i

if(c[i][j]!=max && c[i][j]>flow[i][j])

money[i][j]=moneypre[i][j];

if((c[i][j]!=max && c[i][j]==flow[i][j]) || (c[i][j]==max && flow[i][j]==max)) money[i][j]=max;}

if(i>j){

if( flow[j][i]>0 )

money[i][j]=-moneypre[j][i];

if(flow[j][i]==0)

money[i][j]=max;}

}

for(i=0;i

for(j=0;j

{

if(i==j)

money[i][j]=0;

if(money[i][j]==-max)

money[i][j]=max;

}

}

//----------------------------------END modifymoney()----------------------------------//

//----------------------------采用逐次逼近法得到一条增广链----------------------------// void approach()

{

int pf[n],ptf[n]={0,0,0,0,0}; //当N变动时，0的个数应与N一致

int min=max;

int i,j,flag;

for(j=0;j

pt[j]=money[0][j]; //直接距离做初始解

do{

flag=1;

for(j=0;j

pf[j]=pt[j]; //将上一次得到的路径迭代结果保存入pf[]

for(i=0;i

{

min=pt[i];

for(j=0;j

{

if(min>(pt[j]+money[j][i]))

min=pt[j]+money[j][i];

}

ptf[i]=min;

}

for(i=0;i

{

pt[i]=ptf[i];

if(pf[i]!=pt[i])

flag=0; //两次迭代的值不同,继续

}

}while(flag==0);

j=n-1;

for(i=0;i

if(pt[i]+money[i][j]==pt[j])

{

p[j]=i+1; //p[j]中的下标从1开始

if(p[j]==1) break;

j=i;

i=-1;

}

for(i=0;i

D[i]=pt[i];

}

//------------------------------END approach()------------------------------//

void main()

{

int i,j;

Dijkstra();

while( 1 )

{

modify(); //调整流量矩阵

maxflow=0;

for(j=0;j

{

if(flow[0][j]!=max)

maxflow+=flow[0][j];

}

if(maxflow==stream) break;

modifymoney();

approach(); //采用逐次逼近法得到一条增广链

}

cout

for(i=0;i

{

for(j=0;j

cout

cout

}

cout

for(i=0;i

{

for(j=0;j

cout

}


相关文章

  • 实验三:使用matlab求解最小费用最大流算问题

    • 北京联合大学 实验报告 项目名称: 运筹学专题实验报告 学 院: 自动化 专 业: 物流工程 班 级: 1201B 学 号:[1**********]81 姓 名: 管水城 成 绩: 2015 年 5 月 6 日 实验三:使用matlab ...查看


  • 数学建模图论

    • 图论 一．最短路问题 问题描述:寻找最短路径就是在指定网络中两结点间找一条距离最小的路.最短路不仅仅指一般地理意义上的距离最短, 还可以引申到其它的度量, 如时间.费用.线路容量等. 将问题抽象为赋权有向图或无向图G ,边上的权均非负 对每 ...查看


  • 图的遍历与最小生成树

    • 二中信息学奥赛培训讲义 图论1--图的遍历与图的最小生成树 一.图的遍历 图的遍历:从图的某顶点出发,访问图中所有顶点,并且每个顶点仅访问一次.在图中,访问部分顶点后,可能又沿着其他边回到已被访问过的顶点.为保证每一个顶点只被访问一次,必须 ...查看


  • 旅行商问题的几种求解算法比较

    • 旅行商问题的几种求解算法比较 作者: (xxx学校) 摘要:TSP问题是组合优化领域的经典问题之一,吸引了许多不同领域的研究工作者,包括数学,运筹学,物理,生物和人工智能等领域,他是目前优化领域里的热点.本文从动态规划法,分支界限法,回溯法 ...查看


  • 试论网络流算法中模型的优化与选择

    • 福建师大附中 周 成[内容摘要] 近年来,在国内信息学竞赛(尤其是国家队选拔赛).国际信息学竞赛中,多次出现应用网络流算法求解的试题,网络流算法已是信息学奥赛选手必须掌握的算法.本文主要探讨不同网络模型的构造对问题解决的效率的影响,以及如何 ...查看


  • 论网络流算法中模型的优化与选择

    • 论网络流算法中模型的优化与选择 福建师大附中周成 [内容摘要]近年来,在国内信息学竞赛(尤其是国家队选拔赛).国际信息学竞赛中,多次出现应用网络流算法求解的试题,网络流算法已是信息学奥赛选手必须掌握的算法.本文主要探讨不同网络模型的构造对问 ...查看


  • 背包问题九讲

    • 背包问题九讲2.0RC1 崔添翼(TianyiCui)* 2011-09-28† 本文题为<背包问题九讲>,从属于<动态规划的思考艺术>系列. 这系列文章的第一版于2007年下半年使用EmacsMuse制作,以HTM ...查看


  • 背包问题九讲_DOC版

    • 背包问题九讲 2008.4 背包问题九讲 v1.0 目录 第一讲 01背包问题 第二讲 完全背包问题 第三讲 多重背包问题 第四讲 混合三种背包问题 第五讲 二维费用的背包问题 第六讲 分组的背包问题 第七讲 有依赖的背包问题 第八讲 泛化 ...查看


  • 光明市的菜篮子工程

    • 环游路径和单个路径(每次都从收购点出发)比较求解: 第三问应该以增加量最合理为目标函数进行求解. 光明市的菜篮子工程 摘要 光明市菜篮子工程的开销主要由蔬菜调运费用和短缺损失两部分组成,要使开销最小,就要使这两部分的费用总和最小.因此路径的 ...查看


热门内容