最大网络流问题 ，谁能帮我把题目的代码写一下，用c++或c写。题目如下：

#include<iostream>

#include<queue>

using namespace std;

#define INF 1000000000

struct node{

int from;

int to;

int flow;

}f[1000];

int n,m;

int maxf[1000];

bool vis[1000];

void bfs()

{

queue<int> p;

int i;

vis[1]=true;

ppush(1);

while(!pempty())

{

int q=pfront();

ppop();

for(i=1;i<=m;i++)

{

if(f[i]from==q)

{

if(vis[f[i]to]==0)

{

ppush(f[i]to);

vis[f[i]to]=true;

}

maxf[f[i]to]+=min(f[i]flow,maxf[q]);

}

}

}

cout<<maxf[n]<<endl;

}

int main()

{

while(cin>>n>>m)

{

int i;

for(i=1;i<=m;i++)

{

cin>>f[i]from>>f[i]to>>f[i]flow;

}

memset(maxf,0,sizeof(maxf));

memset(vis,0,sizeof(vis));

maxf[1]=INF;

bfs();

}

return 0;

}

BFS解最大流。

可行流是最大流的充分必要条件是无增广链。

从可行流和无增广链关系来看，就可以知道一种寻求最大流的方法：从一个可行流开始，寻求关于这个可行流的可增广链，若存在，则可以经过调整，得到一个新的可行流，其流量比原来的可行流要大，重复这个过程，直到不存在关于该流的可增广链时就得到了最大流。 

v这种算法由Ford 和 Fulkerson于1956年提出，故又称Ford-Fulkerson标号法。

扩展资料

对一个网络的某些点指定为发点，规定出提供能力；某些点指定为收点，规定出接收能力。

若一个流对每一发点满足总流出量与总流入量之差不大于提供能力，对每一收点满足总流入量与总流出量之差不小于接收能力，则称这个流为可行流。

可行流存在的充分必要条件：对所有顶点子集s都满足:由s到s的弧的总容量，不小于s中的收点总接收能力与s中的发点的总提供能力之差。

这个定理在图论中有许多应用。

图论中的一种理论与方法，研究网络上的一类最优化问题 。1955年 ，TE哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，LR 福特和 DR 富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论。所谓网络或容量网络指的是一个连通的赋权有向图 D= （V、E、C） ， 其中V 是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起点和一个终点。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去起点和终点以外，在所有中途点要求保持流入量和流出量是平衡的。如果把下图看作一个公路网，顶点v1…v6表示6座城镇，每条边上的权数表示两城镇间的公路长度。现在要问 ：若从起点v1将物资运送到终点v6去 ，应选择那条路线才能使总运输距离最短这样一类问题称为最短路问题 。 如果把上图看作一个输油管道网 ， v1 表示发送点，v6表示接收点，其他点表示中转站 ，各边的权数表示该段管道的最大输送量。现在要问怎样安排输油线路才能使从v1到v6的总运输量为最大。这样的问题称为最大流问题。

最大流理论是由福特和富尔克森于 1956 年创立的 ，他们指出最大流的流值等于最小割(截集)的容量这个重要的事实，并根据这一原理设计了用标号法求最大流的方法，后来又有人加以改进，使得求解最大流的方法更加丰富和完善 。最大流问题的研究密切了图论和运筹学，特别是与线性规划的联系，开辟了图论应用的新途径。

假设G(V,E) 是一个有限的有向图，它的每条边(u,v)∈E都有一个非负值实数的容量c(u,v) 。如果(u,v)不属于E，我们假设c(u,v) = 0 。我们区别两个顶点：一个源点s和一个汇点t。一道网络流是一个对于所有结点u和v都有以下特性的实数函数f:V×V→R 容量限制 (Capacity Constraints): f(u,v)≤c(u,v)一条边的流不能超过它的容量。 斜对称 (Skew Symmetry): f(u,v)=-f(v,u)由u到v的净流必须是由v到u的净流的相反（参考例子）。（既然要看网络流，这是一定要知道的） 流守恒 (Flow Conservation): 除非u=s或u=t，否则Σ（w∈V）f(u,w)=0 一结点的净流是零，除了“制造”流的源点和“消耗”流的汇点。 注意f(u,v) 是由u到v的净流。如果该图代表一个实质的网络，由u到v有 4 单位的实际流及由v到u有 3 单位的实际流，那么f(u,v) = 1 及f(v,u) = − 1。

边的剩余容量 (Residual Capacity)是cf(u,v) =c(u,v)−f(u,v)。这定义了以Gf(V,Ef)表示的剩余网络 (Residual Network)，它显示可用的容量的多少。留意就算在原网络中由u到v没有边，在剩余网络乃可能有由u到v的边。因为相反方向的流抵消，减少由v到u的流等于增加由u到v的流。扩张路径 (Augmenting Path)是一条路径 (u1,u2uk)，而u1 =s、uk=t及cf(ui,ui+ 1) > 0，这表示沿这条路径传送更多流是可能的。

1,双代号时标网络计划是以时间坐标为尺度编制的网络计划，时标网络计划中应以实箭线表示工作，以虚箭线表示虚工作，以波形线表示工作的自由时差。

2,双代号时标网络计划必须以水平时间坐标为尺度表示工作时间。时标的时间单位应根据需要在编制网络计划之前确定，可为时、天、周、月或季。

3,时标网络计划中所有符号在时间坐标上的水平投影位置，都必须与其时间参数相对应。节点中心必须对准相应的时标位置。

4,时标网络计划中虚工作必须以垂直方向的虚箭线表示，有自由时差时加波形线表示。

5,双代号时标网络图总时差的计算公式=紧后工作的总时差+本工作与该紧后工作之间的时间间隔所得之和的最小值

6,计算哪个工作的总时差，就以哪个工作为起点工作，寻找通过该工作的所有线路，然后计算

各条线路的波形线的长度和，波形线长度和的最小值就是该工作的总时差。

解决最小费用最大流问题，一般有两条途径。一条途径是先用最大流算法算出最大流，然后根据边费用，检查是否有可能在流量平衡的前提下通过调整边流量，使总费用得以减少？只要有这个可能，就进行这样的调整。调整后，得到一个新的最大流。

然后，在这个新流的基础上继续检查，调整。这样迭代下去，直至无调整可能，便得到最小费用最大流。这一思路的特点是保持问题的可行性（始终保持最大流），向最优推进。另一条解决途径和前面介绍的最大流算法思路相类似，一般首先给出零流作为初始流。这个流的费用为零，当然是最小费用的。然后寻找一条源点至汇点的增流链，但要求这条增流链必须是所有增流链中费用最小的一条。如果能找出增流链，则在增流链上增流，得出新流。将这个流做为初始流看待，继续寻找增流链增流。这样迭代下去，直至找不出增流链，这时的流即为最小费用最大流。这一算法思路的特点是保持解的最优性（每次得到的新流都是费用最小的流），而逐渐向可行解靠近（直至最大流时才是一个可行解）。

由于第二种算法和已介绍的最大流算法接近，且算法中寻找最小费用增流链，可以转化为一个寻求源点至汇点的最短路径问题，所以这里介绍这一算法。

在这一算法中，为了寻求最小费用的增流链，对每一当前流，需建立伴随这一网络流的增流网络。例如图 1 网络G 是具有最小 费用的流，边旁参数为c(e),f(e),w(e），而图 2 即为该网络流 的增流网络G′。增流网络的顶点和原网络相同。按以下原则建 立增流网络的边：若G中边（u，v）流量未饱，即f(u,v) < e(u,v），则G ' 中建边（u,v），赋权w ' (u,v)=w(u,v）；若G中边（u,v）已有流量，即f(u,v）〉0，则G′中建边（v,u），赋权w′（v,u) =-w(u,v）。建立增流网络后，即可在此网络上求源点至汇点的最短路径，以此决定增流路径，然后在原网络上循此路径增流。这里，运用的仍然是最大流算法的增流原理，唯必须选定最小费用的增流链增流。

计算中有一个问题需要解决。这就是增流网络G ′中有负权边，因而不能直接应用标号法来寻找x至y的最短路径，采用其它计算有负权边的网络最短路径的方法来寻找x至y的最短路径，将 大大降低计算效率。为了仍然采用标号法计算最短路径，在每次建立增流网络求得最短路径后，可将网络G的权w(e）做一次修正，使再建的增流网络不会出现负权边，并保证最短路径不至于因此而改变。下面介绍这种修改方法。当流值为零，第一次建增流网络求最短路径时，因无负权边，当然可以采用标号法进行计算。为了使以后建立增流网络时不出现负权边，采取的办法是将 G中有流边（f(e)>0）的权w(e）修正为0。为此， 每次在增流网络上求得最短路径后，以下式计算G中新的边权w (u,v）：

w (u,v)=L(u)-L(v)+w(u,v) ()

式中 L(u),L(v) -- 计算G′的x至y最短路径时u和v的标号值。第一次求最短径时如果（u,v）是增流路径上的边， 则据最短 路径算法一定有 L(v)=L(u)+w ' (u,v)=L(u)+w(u,v）， 代入（）式必有

w″（u,v)=0。

如果（u,v）不是增流路径上的边，则一定有：

L(v）≤L(u)+w(u,v）， 代入（）式则有 w ”(u,v）≥0。

可见第一次修正w(e）后，对任一边，皆有w(e）≥0， 且有流 的边（增流链上的边），一定有w(e)=0。以后每次迭代计算，若 f(u,v)>0，增流网络需建立（v,u）边，边权数w ' (v,u)=-w(u,v) =0，即不会再出现负权边。 此外，每次迭代计算用（）式修正一切w(e）， 不难证明对每一条x至y的路径而言，其路径长度都同样增加L(x)-L(y）。因此，x至y的最短路径不会因对w(e）的修正而发生变化。

计算步骤

⒈ 对网络G=[V,E,C,W]，给出流值为零的初始流。

⒉ 作伴随这个流的增流网络G′=[V′，E′，W′]。G′的顶点同G：V′=V。若G中f(u,v)<c(u,v），则G′中建边（u,v），w(u,v)=w(u,v）。若G中f(u,v)>0，则G′中建边（v,u），w′（v,u)=-w(u,v）。

⒊ 若G′不存在x至y的路径，则G的流即为最小费用最大流， 停止计算；否则用标号法找出x至y的最短路径P。

⒋ 根据P，在G上增流：对P的每条边（u,v），若G存在（u,v），则（u,v）增流；若G存在（v,u），则（v,u）减流。增（减）流后，应保证对任一边有c(e）≥ f(e）≥0。

⒌ 根据计算最短路径时的各顶点的标号值L(v），按下式修 改G一切边的权数w(e):

L(u)-L(v)+w(e）→w(e）。

⒍ 将新流视为初始流，转2。

最大流理论是由福特和富尔克森于1956年创立的，他们指出最大流的流值等于最小割(截集)的容量这个重要的事实，并根据这一原理设计了用标号法求最大流的方法，后来又有人加以改进，使得求解最大流的方法更加丰富和完善。最大流问题的研究密切了图论和运筹学，特别是与线性规划的联系，开辟了图论应用的新途径。

最大流问题仅注意网络流的流通能力，没有考虑流通的费用。实际上费用因素是很重要的。例如在交通运输问题中，往往要求在完成运输任务的前提下，寻求一个使总运输费用最省的运输方案，这就是最小费用流问题。如果只考虑单位货物的运输费用，那么这个问题就变成最短路问题。由此可见，最短路问题是最小费用流问题的基础。现已有一系列求最短路的成功方法。最小费用流(或最小费用最大流)问题，可以交替使用求解最大流和最短路两种方法，通过迭代得到解决。网络最大流问题和它的对偶问题——最小截问题，是一对经典组合优化问题，它们在许多工程领域和科学领域有重要的应用，是计算机科学和运筹学重要的内容，最大流问题已经有40多年的研究历史，近年来，随着各种网络的飞速发展，最大流问题的研究也取得了很大的进展，对最大流问题研究做了详细的总结，并对下一步研究趋势进行了预测。

function [f,wf,No]=MaxFlowMinCut_Me(n,C)

% 利用Ford--Fulkerson 标号法求最大流算法的MATLAB 程序代码

% f %显示最大流

% wf %显示最大流量

% No %显示标号, 由此可得最小割

% n 节点个数

% C %弧容量

% Example:

% n=8;

% C=[0 5 4 3 0 0 0 0

% 0 0 0 0 5 3 0 0

% 0 0 0 0 0 3 2 0

% 0 0 0 0 0 0 2 0

% 0 0 0 0 0 0 0 4

% 0 0 0 0 0 0 0 3

% 0 0 0 0 0 0 0 5

% 0 0 0 0 0 0 0 0];

% [f,wf,No]=MaxFlowMinCut_Me(n,C)

for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流

for(i=1:n)No(i)=0;d(i)=0;end %No,d 记录标号

while(1)

No(1)=n+1;d(1)=Inf; %给发点vs 标号

while(1)pd=1; %标号过程

for(i=1:n)if(No(i)) %选择一个已标号的点vi

for(j=1:n)if(No(j)==0&f(i,j)<C(i,j)) %对于未给标号的点vj, 当vivj 为非饱和弧时

No(j)=i;d(j)=C(i,j)-f(i,j);pd=0;

if(d(j)>d(i))d(j)=d(i);end

elseif(No(j)==0&f(j,i)>0) %对于未给标号的点vj, 当vjvi 为非零流弧时

No(j)=-i;d(j)=f(j,i);pd=0;

if(d(j)>d(i))d(j)=d(i);end;end;end;end;end

if(No(n)|pd)break;end;end %若收点vt 得到标号或者无法标号, 终止标号过程

if(pd)break;end %vt 未得到标号, f 已是最大流, 算法终止

dvt=d(n);t=n; %进入调整过程, dvt 表示调整量

while(1)

if(No(t)>0)f(No(t),t)=f(No(t),t)+dvt; %前向弧调整

elseif(No(t)<0)f(No(t),t)=f(No(t),t)-dvt;end %后向弧调整

if(No(t)==1)for(i=1:n)No(i)=0;d(i)=0; end;break;end %当t 的标号为vs 时, 终止调整过程

t=No(t);end;end; %继续调整前一段弧上的流f

wf=0;for(j=1:n)wf=wf+f(1,j);end

end

当物质流或信息流通过给定的网络时（图1）,在流过每条边的流量xij不超过该边允许通过的流量cij的条件下,求出从发点s向收点t输出的最大流量f，即在满足的条件下,使f最大。最大流量问题是一个特殊的线性规划问题，有许多求解方法。一种有效的计算方法是福特-富尔克森法，它是根据最大流量-最小割集原理，通过标号算法，求出在上述约束条件下从发点s到收点t的最大流量f 的数值。其计算步骤如下：①绘制一个能满足上述约束条件的网络可行流（图2）。边上的数字为允许流量cij，括号内的数字为给定的可行流。②找出一条增广链。增广链是指从发点s到收点t的链中，满足正向边上xij<cij和反向边上xji>0的链。图2中用粗线表示的{vs，v2,v3,v4,v6,vt} 是一条增广链。其中v2,v3为反向边,其余均为正向边。③调整可行流,即在增广链的各边上,属正向边加上一个修正量ε,属反向边减去一个修正量ε,即xij+εj，xji-εj。εj值由下式决定:当xij<cij时