最小费用最大流

最小费用最大流

动物是怎么睡觉的-家常炖鱼

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

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

#include"iostream.h"

#definemax10000

#definen5//根据不同问题可修改大小

#definestream10//根据不同问题可修改

//最大容量矩阵

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,ma

x,0}};

//增广链向量

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

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

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

intmaxflow;//设置最大流量

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

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

{

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

inti,j,k,vl,pre;

intmin;

intinf=20000;

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

for(i=0;i

{

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

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

elsep[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<<"Vs到Vt的最短路径为(长和径):n";

for(i=0;i

{

if(i=n-1){

cout<

pre=p[i];

while(pre!=0)

{

cout<<"<--"<

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

}

cout<<"n";}

}

}

//-----------------------------------ENDDijkstra()-----------------------------------------//

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

voidmodify()

{

inti,min;

intpre;

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;

}

}

//----------------------------------ENDmodify()----------------------------------//

//--------------------------------调整费用矩阵money[][]-----------------------------//

voidmodifymoney()

{

inti,j;

intmoneypre[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;

}

}

//----------------------------------ENDmodifymoney()----------------------------------//

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

voidapproach()

{

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

intmin=max;

inti,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];

}

//------------------------------ENDapproach()------------------------------//

voidmain()

{

inti,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<<"流量矩阵：n";

for(i=0;i

{

for(j=0;j

cout<

cout<<"n";

}

cout<<"费用矩阵：n";

for(i=0;i

{

for(j=0;j

cout<

cout<<"n";

}

}