下载文档原格式
最大流的概念最大流（Maximum Flow）是指在一个有向图中，给每条边一个容量限制，然后寻找一条从源点到汇点的路径，使得路径上的每条边的流量都不超过其容量限制的最大值。
最大流问题是网络流理论中的一种经典问题，具有广泛的应用领域，如网络优化、流量分配、资源调度等。
最大流问题可以用图论中的图来进行模型表示，其中图中的节点表示流经的位置，边表示流量通路，每条边还有一个容量值，表示该边所能承载的最大流量。
图中通常包括一个源点（Source）和一个汇点（Sink），各个节点与源点和汇点之间的连接关系构成了一个流量网络。
每个节点上的流量是指通过该节点的流量总和，而边上的流量是指该边上的实际流量。
最大流问题的求解可以采用不同的算法，其中最常见的是Ford-Fulkerson算法和Edmonds-Karp算法。
下面将对这两种算法进行详细介绍。
1. Ford-Fulkerson算法Ford-Fulkerson算法是最大流问题的经典算法，它的思想是不断寻找增广路径，并通过增加该路径上各边的流量来增加整个流量网络的流量。
算法的基本步骤如下：(1) 初始化流量网络的流量为0。
(2) 通过任意的路径查找算法（如深度优先搜索）找到一条从源点到汇点的增广路径。
(3) 在该增广路径上增加流量的值为该路径上残余容量的最小值。
(4) 更新整个流量网络中各边的残余容量和反向边的流量。
(5) 重复步骤2至4，直到无法找到增广路径为止。
2. Edmonds-Karp算法Edmonds-Karp算法是Ford-Fulkerson算法的一种改进，它通过使用广度优先搜索来寻找增广路径，使得算法的时间复杂度优于Ford-Fulkerson算法。
算法的具体步骤如下：(1) 初始化流量网络的流量为0。
(2) 通过广度优先搜索查找一条从源点到汇点的最短增广路径。
(3) 在该增广路径上增加流量的值为该路径上残余容量的最小值。
(4) 更新整个流量网络中各边的残余容量和反向边的流量。
比流量的计算公式
网络流量是指在网络中传输的数据量，通常用比特（bit）或字节（byte）来表示。
计算网络流量的公式是：带宽（单位时间内能传输的数据量）乘以在线时间。
网络带宽是指网络的传输速率，通常用Mbps（兆比特每秒）来衡量。
在线时间指设备或网络在一段时间内的运行时间，通常用小时或天数来表示。
例如，一个企业在一天内使用了100Mbps的带宽，设备在线时间为12小时。
那么该企业在这一天的网络流量为：
100 Mbps × 12 hours = 1,440,000 Mb
将这个数字转换成字节，可以使用以下公式：
1,440,000 Mb × 1,000,000 bits/Mb ÷ 8 bits/byte = 180,000,000 bytes
这意味着该企业在这一天内传输了180,000,000个字节的数据。
如果将这个数字转换成更易于理解的单位，可以使用以下公式：
180,000,000 bytes ÷ 1,024 bytes/kilobyte ÷ 1,024 kilobytes/megabyte = 171.7 MB
因此，该企业在这一天内传输了约171.7MB的数据。
需要注意的是，计算网络流量时还应考虑到网络传输中的数据包重传、网络丢包等因素。
此外，不同类型的数据传输也会对网络流量产生不同的影响。
例如，视频流媒体会占用更多的网络带宽和流量，而文本传输则占用较少的带宽和流量。
计算网络流量的公式是带宽乘以在线时间。
了解网络流量的计算方法可以帮助企业或个人更好地控制网络使用和优化网络性能。
最大流算法在网络优化中的应用最大流算法是一种常用的图论算法，用于解决网络中流量分配的问题。
它在许多领域中都有广泛的应用，尤其在网络优化中发挥着重要的作用。
本文将介绍最大流算法的原理和几个具体应用案例。
一、最大流算法原理最大流算法的核心思想是通过构建一个有向图来描述网络流量的传递。
在图中，节点代表网络中的顶点或交叉点，边表示两个节点之间的连接。
每条边上都有一个容量，表示该边能够传递的最大流量。
最大流算法通过从源节点（Source）向汇节点（Sink）不断推送流量，并更新路径上的容量，直到不能再推送为止。
这样，最终的结果就是源节点向汇节点的最大流量。
二、最大流算法的应用1. 网络流量优化在计算机网络中，最大流算法被广泛应用于网络流量的优化问题。
通过最大流算法，可以确定从源节点到汇节点的最大可用带宽，从而实现网络资源的合理分配和利用。
在网络拓扑结构复杂的大型系统中，最大流算法能够帮助我们优化网络性能，提高数据传输效率。
2. 电力网络调度在电力系统中，最大流算法可以用来解决电力网络调度问题。
通过最大流算法，可以确定发电站到用户之间的最大功率传输，从而实现电力的高效分配。
在电力系统的规划和管理中，最大流算法能够帮助我们确保电力供需平衡，提高电网的可靠性和稳定性。
3. 交通网络优化最大流算法还可以用于交通网络的优化。
通过最大流算法，可以确定交通网络中各路段的最大通过能力，从而实现交通流量的合理调度。
在城市交通规划和管理中，最大流算法能够帮助我们减少交通拥堵，提高交通效率，优化交通资源的利用。
4. 供应链管理在供应链管理中，最大流算法可以用来优化物流路径和资源分配。
通过最大流算法，可以确定供应链中各个节点之间的最大货物流量，从而实现供应链的高效运作。
在供应链的规划和执行中，最大流算法能够帮助我们减少成本，提高服务水平，实现资源的最优配置。
三、总结最大流算法在网络优化中具有广泛的应用。
通过构建有向图模型，最大流算法能够帮助我们解决网络中的流量分配问题，实现资源的最优配置和利用。
网络流问题及其求解方法网络流问题是指在一个有向图中，给定网络的容量限制，找到从源点到汇点的最大流量。
这个问题在实际生活中有着广泛的应用，比如在运输、通信、电力等领域。
本文将介绍网络流问题以及几种常见的求解方法。
1. 网络流问题的定义网络流问题可以用有向图来表示。
图中的每条边具有一个容量，表示该边能够通过的最大流量。
同时，图中有一个源点，表示流量的起点，以及一个汇点，表示流量的终点。
问题的目标是找到从源点到汇点的最大流量。
2. 求解方法一：最短增广路径算法最短增广路径算法是一种基于广度优先搜索的方法。
算法的思想是在图中不断寻找增广路径，即从源点到汇点且每条边的流量都满足容量限制的路径。
然后通过增加路径上的流量来更新网络的流量，并继续寻找下一个增广路径。
直到找不到增广路径为止，即可得到最大流量。
3. 求解方法二：最大流-最小割定理最大流-最小割定理是网络流问题的一个重要性质。
该定理指出，网络的最大流量等于它的最小割。
最小割是指将网络分成两个部分，一部分包含源点，另一部分包含汇点，并且割边的总容量最小。
根据该定理，可以通过寻找最小割来求解网络流问题。
4. 求解方法三：Ford-Fulkerson算法Ford-Fulkerson算法是一种经典的求解网络流问题的方法。
该算法通过不断寻找增广路径来更新网络的流量，直到无法再找到增广路径为止。
算法的关键在于如何选择增广路径，一种常见的选择策略是使用深度优先搜索。
Ford-Fulkerson算法的时间复杂度与最大流的大小有关，一般情况下为O(fE)，其中f为最大流量，E为图中边的数量。
总结：网络流问题是一个重要的优化问题，在实际应用中具有广泛的应用。
本文介绍了网络流问题的定义以及几种常见的求解方法，包括最短增广路径算法、最大流-最小割定理和Ford-Fulkerson算法。
这些算法都可以有效地求解网络流问题，并在实践中得到广泛应用。
通过研究网络流问题及其求解方法，可以为实际问题的建模和解决提供有力的工具。
最大流算法在网络流量问题中的应用网络流量问题是指在网络中传输数据时的信息流量问题。
这个问题常常需要使用最大流算法来解决。
最大流算法是一种用于寻找网络中的最大物质量传输量的算法。
最大流算法在通信、交通、水文、金融等领域中有广泛的应用。
网络流量问题与最大流算法的关系在计算机网络中，数据包的传输由源节点和目标节点之间的通道组成。
当存在网络堵塞现象时，通道的容量会限制数据包的传输速度和数量。
这时，就需要最大流算法来计算网络中的最大物质量传输量，帮助解决网络拥塞问题。
最大流算法的原理最大流问题可以转化为寻找网络中的最小割。
在一个网路图中，如果我们要将某个节点上的信息流送到另一个节点，那么需要通过一个网络图，网络图基于给定的能力值设置了容量。
在这种情况下，最大流算法可以算出按给定流量分布流到每个节点的最大物质量。
最大流算法采用了一种找到最大物质量传输量的方法。
这个方法被称为增广路径方法。
这种方法利用了模型中的残存图，残存图是指将当时最大流中占据着最大流的边剔除，然后代入新增的增广路径。
最大流算法的实现最大流算法可以使用多种方法来实现。
其中，最常用的方法是Ford-Fulkerson算法及其改进的算法。
Ford-Fulkerson算法是一种流量增量算法，它计算网络中所有从源节点到汇节点的最大物质量流。
这个算法的核心是一个递增路径搜寻的过程，在每一次搜寻过程中增大这条路径的流量。
除了Ford-Fulkerson算法，还有其他的最大流算法。
比如说，预流推进算法和Edmonds-Karp算法。
其中，预流推进算法利用了前向推进和后向收缩两种操作，在实现上更加复杂。
Edmonds-Karp算法则采用了广度优先搜索法，能够快速找到增广路径，实现上也比较直观。
最大流算法的应用最大流算法在计算机网络和信息科学领域中有广泛的应用。
它可以用来优化网络中的资源分配和流量控制，提高网络性能和可靠性。
在视频流媒体和云计算等领域中，最大流算法可以用来优化资源分配，提高多媒体数据传输质量。
网络流算法（NetworkFlow）网络流算法，是指寻找网络流问题的解的算法，它是一类重要的组合优化问题，被广泛应用于计算机科学及工程领域。
网络流是个有向图，它模拟了许多实际问题，如输电方案、货物运输、油管输送和信息传输等。
网络流算法的目的是在给定的网络流中，尽可能地将流量从源点流向汇点，同时满足各个节点的容量约束和流量平衡约束。
本文将介绍网络流模型的构建和基本算法。
一、网络流模型的构建网络流模型是一个有向图G=(V,E)，其中V表示节点集合，E表示边集合。
每条边都有一个容量c(e)表示其流量的最大值。
设源点为s，汇点为t，则网络流模型可以表示为一个三元组(N,s,t)，即：N=(V,E) s∈V t∈V s≠t在网络流模型中，源点始终是起点，汇点始终是终点。
我们在模型中引入一个源汇节点s'和汇源节点t'，并连接源点和汇点，得到源汇图G'=(V,E')，其中：E'=E∪{(s',s,c(s,t))}∪{(t,t',c(s,t))}即，在原图的基础上，加入两个新的虚拟节点s'和t'，并连接到源点和汇点。
这样构造的网络流模型中，所有的节点都满足容量和流量平衡约束。
在网络流问题中，我们需要求解最大流或最小割，以满足约束条件，并且尽可能地提高网络的利用率。
二、网络流的基本概念和算法1. 流量和容量网络流图中，首先需要确定每条边的容量和流量。
流量指的是通过该边的流量大小，容量指的是该边能够承受的最大流量。
在网络流模型中，每条边的容量是一个正实数，而流量可以是任意实数。
流量和容量通常表示为f(e)和c(e)。
2. 割在网络流模型中，割是一种对源汇图做出的划分，其中源点s和汇点t被分为两个集合S和T。
网络流通过割的概念来定义障碍物，即对流量的限制。
在网络流图中，割C(S,T)是指将源点s和汇点t割成两部分的划分，C(S,T)满足：s∈S t∈T S∩T=∅根据割的定义，可将所有割分为最小割和最大割。
⽹络流（最⼤流-Dinic算法）⽹络流定义 在图论中，⽹络流（Network flow）是指在⼀个每条边都有容量（Capacity）的有向图分配流，使⼀条边的流量不会超过它的容量。
通常在运筹学中，有向图称为⽹络。
顶点称为节点（Node）⽽边称为弧（Arc）。
⼀道流必须匹配⼀个结点的进出的流量相同的限制，除⾮这是⼀个源点（Source）──有较多向外的流，或是⼀个汇点（Sink）──有较多向内的流。
⼀个⽹络可以⽤来模拟道路系统的交通量、管中的液体、电路中的电流或类似⼀些东西在⼀个结点的⽹络中游动的任何事物。
————维基百科 最⼤流 正如可以通过将道路交通图模型化为有向图来找到从⼀个城市到另⼀个城市之间的最短路径，我们也可以将⼀个有向图看做是⼀个“流⽹络”并使⽤它来回答关于物料流动⽅⾯的问题。
设想⼀种物料从产⽣它的源结点经过⼀个系统，流向消耗该物料的汇点这样⼀个过程。
源结点以某种稳定的速率⽣成物料，汇点则以同样的速率消耗物料。
从直观上看，物料在系统中任何⼀个点上的“流量”就是物料移动的速率。
这种流⽹络可以⽤来建模很多实际问题，包括液体在管道中的流动、装配线上部件的流动、电⽹中电流的流动和通信⽹络中信息的流动。
我们可以把流⽹络中每条有向边看做是物料的⼀个流通通道。
每条通道有限定的容量，是物料流经该通道时的最⼤速率，如⼀条管道每⼩时可以流过200加仑的液体。
流⽹络中的结点则是通道的连接点。
除了源结点和终结点外，物料在其他结点上只是流过，并不积累或聚集。
换句话说，物料进⼊⼀个结点速率必须与其离开该结点的速率相等。
这个性质称为“流量守恒”，这⾥的流量守恒与Kirchhoff电流定律等价。
在最⼤流问题中，我们希望在不违反任何容量限制的情况下，计算出从源结点运送物料到汇点的最⼤速率。
这是与流⽹络有关的所有问题中最简单的问题之⼀().，这个问题可以由⾼效的算法解决。
⽽且，最⼤流算法中的⼀些基本技巧可以⽤来解决其他⽹络流问题。
最大流算法在网络问题中的应用网络问题是计算机科学中的一个重要领域，主要研究节点之间的连通性，以及数据在网络中的传输和处理方式。
网络问题的解决方法之一就是最大流算法。
最大流算法可以用来求解网络流问题，是一种常用的优化算法。
下面将详细介绍最大流算法在网络问题中的应用。
一、最大流算法的定义最大流算法（Maximum Flow Algorithm）是计算最大流问题的常用算法，用于解决网络流问题。
最大流问题是在网络中从源点s 到汇点t的最大可行流问题，也可以理解为管道输送液体的最大流量问题。
最大流算法求解的本质就是如何找到一条从源点到汇点的路径，并计算出最大流量，以使所有流量达到最大。
二、最大流算法的应用最大流算法的应用非常广泛，在交通、卫星通信、电信等领域均有广泛应用。
下面分别从交通、卫星通信和电信三个方面来介绍最大流算法的应用。
1、交通领域在交通领域，最大流算法可以应用于城市道路布局规划、交通信号灯调度和公交线路规划等问题。
以城市道路布局规划为例，我们可以通过最大流算法来确定城市中心和周边地区之间的交通流量。
这样，我们就可以在城市道路规划过程中根据交通流量分配道路宽度和车行道数量，以确保道路能够承载最大交通流量。
2、卫星通信领域在卫星通信领域，最大流算法可以应用于网络拓扑设计、路由设计和带宽分配等问题。
通过最大流算法，我们可以确定卫星通信网中每个节点之间的最大传输速率，以便于选择最佳的路径或设计最优的路由方案。
此外，最大流算法也可以用于带宽管理，以确保卫星通信网中的每个节点都能够按照其需求获得足够的带宽。
3、电信领域在电信领域，最大流算法可以应用于网络拓扑设计、路由设计和负载均衡等问题。
电信网络中的节点之间互相连通，通过最大流算法，我们可以确定节点之间的最大传输速率，并根据传输速率设计最优的路由方案，以确保数据传输的完整性和可靠性。
此外，最大流算法还可以用于网络负载均衡，以确保所有节点的负载能够均衡分配。
文献综述数学与应用数学网络最大流问题算法研究最大流问题是指在一定的条件下,要求流过网络的物流、能量流、信息流等流量为最大的问题[2].最大流问题已有50多年的研究历史,这段时期内,人们建立了最大流问题较为完善的理论,同时开发了大量的算法.如Ford和Fulkerson增截轨算法、Dinic阻塞流算法、Goldberg推进和重标号算法[6]以及Goldberg和Rao的二分长度阻塞流算法等等,这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的推动作用.近年来,随着计算机科学技术和网络的快速发展,网络最大流问题得到了更深入的研究,并极大地推动了最大流问题的研究进展.然而,研究工作仍未结束:首先,在理论算法研究方面,人们还没有发现最大流问题算法时间复杂度的精确下界,更没有任何一个通用算法达到或接近问题的下界; 其次,在算法的实际性能方面,目前算法的实际性能也不能满足许多应用问题的要求; 同时,最大流问题作为特殊的线性规划问题, 它远比一般线性规划问题容易解决,发现应用领域中的问题和最大流问题的联系可以使应用问题更好地得到解决.因此,关于网络最大流问题的研究具有十分重要的理论意义和实用价值[5].最早的算法是Dantzig[6]提出的网络单纯刑法和Ford和Fulkerson的增载轨算法,他们都是伪多项式时间算法,分别由Dinic、Edmonds和Karp等提出.1973年Dinic首次获得了时间复杂度的核心因子为nm算法.以后的几十年中,最大流算法获得了很大的进展.本文主要介绍的是网络最大流的几种主要算法,其中重点介绍了标号算法的详细过程,其后给出了其在实际中的应用实例,后面介绍了现有的几种主要算法,虽然没有给出具体的程序,但本文目的主要是了解最大流问题的解决思想,读者对网络流算法有更深刻的认识,读者要想了解更多关于最大流问题的研究,详细可以参照Goldberg等人的研究成果, 这些程序在网上都可以轻松得到. 在这里就不再详细讲述.下面简要介绍一下增载轨算法.增载轨算法[5]: 沿剩余网络中从源到汇的有向路径推进流. 增载轨算法包括Ford和Fulkerson 的标号算法、Dinic 的阻塞流算法、Ahuja 和Orlin 的最短增载轨算法等. 1956年, Ford 和Fulkerson 首次发现增载轨算法. 由于Ford 和Fulkerson [3]算法是在剩余网络中任意选择从源到汇的有向路径作为增载轨的, 增载轨的数量可能很多, 最坏情况为()nU O . 因此, Ford 和Fulkerson 算法的时间复杂度为()nmU O , 它是伪多项式时间的. 通过两种好的选择策略可以限制增载轨的数量. 意识每次都选择容量最大的增载轨, 可以把增载轨的数量降为(log )m U O . 但寻找容量最大的增载轨花的代价较大. 另一种策略是每次选择长度最短的增载轨, 使用这种策略可以使增载轨的数量限制在()nm O , Edmonds 和Karp 的最短增载轨算法利用宽度优先搜索在剩余网络中寻找最短增截轨, 该算法的时间复杂度为2()nm O . 为了把上一次构造最短路径的距离信息保留下来提供下一次使用, Dinic 引入了层次网络的阻塞流的概念, Dinic 算法的时间复杂度为2()n m O . Ahuja 和Orlin 采用Goldberg 和Tarjan 引进的距离标号概念构造增载轨, 并改用重标号的方法保留上次构造的距离信息, 这种算法的时间复杂度为2()n m O . Ahuja, Magnanti 和Orlin 在他们的著作中指出Dinic 阻塞流算法可以看作Ahuja 和Orlin [8]最短增载轨算法的一个实现.将容量和最短增载轨结合起来使用, 可以得到(log )nm U O 时间的算法. 1983年, Sleator 和Tarjan 提出了动态树的数据结构并用它实现了Dinic 算法, 使得该算法的时间复杂度降为(log )nm n O [5]. 下面看一下本文要主要介绍的标号算法的情况:定理1[1] 设f 为网络(,,)D V A C =的任一可行流, 流量为f V , (,)S S -为分离s v , t v 的任一割集, 则有(,)f V C S S -≤.定理2[1] Ford-Fulkerson 定理（也称最大流-最小割定理）: 在任何网络(,,)D V A C =中, 从s v 到t v 的最大流的流量等于分离s v , t v 的最小割集的容量.下面介绍的是最大流问题的增广链算法, 步骤为:1、 通过寻找剩余网络中从发点到收点的正项链中每个弧上都有非零剩余容量的链而找到增广链（如果不存在增广链, 该网络已达到最大流）.2、 找出增广链中弧的最小剩余容量c *, 这就是该增广链的剩余容量, 在该增广链中增加流量为c*的流.3、在增广链的每个正向弧的剩余容量中减去c*, 而在每个反向弧的剩余容量中加上c*.返回步骤1.在进行步骤1时, 往往会碰到很多增广链可供选择, 在用这种方法来解决大规模问题时,增广链的正确选择对解决问题的效率是至关重要的.上面说的只是网络最大流问题算法中的一个, 本文将讲述网络最大流问题的几种主要算法, 主要是标号法, 还包括ISAP算法、SAP算法等.对于一个网络最大流问题, 现在有很多求解方法, 如重标号算法、预流推进算法等[6]. 对一个最大流问题也可以用线性规划方法求解, 也就是说, 将一个最大流问题转化为一个线性规划模型, 再用单纯形法求解. 有些情况下运用线性规划模型求解很方便, 而且易于理解[7].这几十年来, 很多著名学者开发出了很多优秀的算法, 由R. K. Ahuja和B. Orlin提出的快速算法是基于Goldberg和Tarjan的算法而得到的一个平行算法, 即预流推进算法[8]. 其对后面学者的研究起了很大的指导作用. 在具有适宜整数边容量的稀疏图中, Gabow的缩进算法是最好的. 而基于Dinic算法结构的那些算法中, 唯一的一个平行算法是由Shiloach和Vishkin给出. Goldberg给出了基于Karzanov预流思想的新算法, 即在剩余网络中寻找最短路径[8]. Gallo和Tarjan等提出通过重优化技术能解决参数最大流中的很多问题, 其是对Goldberg和Tarjan的推重标号法进行的拓展, 进一步优化了最大流问题算法[9].由Ford和Fulkerson提出的增广链算法是基础, Edmonds和Karp提出的另外一个方法是始终沿着最短路径增广, 它利用的是广度优先搜索思想, 这种算法存在一个最坏运行时间. 还有Dinic独自提出的最短路径增广等算法, 这些都对最大流问题的算法研究产生了巨大的影响[10].一直以来,网络最大流的应用都是一项十分有意义的研究工作, 网络流问题的研究者和具体问题的工程师从不同的角度充实着这方面的研究.实践表明, 对许多实际应用问题,如果能找到它和最大流问题的联系, 就可以使问题得到十分有效的解决. 许多应用问题所对应的最大流问题都有比较明显的特征, 充分利用这些特征和挖掘网络特性, 解析典型算法, 充分设计面向应用问题的算法, 这将是网络最大流问题组合算法研究的重要趋势.参考文献[1]廖敏. 运筹学基础与应用[M]. 南京: 南京大学出版社, 2009: 190-197.[2]弗雷德里克•S•希利尔, 杰拉尔德•J•利伯曼（胡运权等译）. 运筹学导论[M]. 北京:清华大学出版社, 2007 : 375-381.[3]L R Ford, D R Fulkerson. Maximum flow through a network. Canadian Journal of Math,1956, 8(5): 399-404.[4]王志强. 网络最大流的新算法[D]. 陕西: 宝鸡文理学院, 2009.[5]张宪超, 陈国良, 万颖瑜等. 网络最大流问题研究进展[J]. 计算机研究与发展学报,2003, 40(9): 1281-1292.[6] A.V. Goldberg and R.E. Tarjan. A new approach to the maximum-flow problem. Journalof the ACM, 1988, 35: 921-940.[7]赵可培. 运筹学[M]. 第二版. 上海: 上海财经出版社, 2008: 243-249.[8]R. K. Ahuja and J.B. Orlin. A fast and simple algorithm for the maximum flow problem.Oper. Res. 1989, 37: 748-759.[9]Maria Grazia Scutella. A note on the parametric maximum flow problem and somerelated reoptimization issues. Ann Oper Res, 2007, 150: 231-244.[10]Robert E. TARJAN. Algorithms for maximum network flow. Mathematical ProgrammingStudy, 1986, 26: 1-11.。
⽹络最⼤流FF算法题⽬描述如题，给出⼀个⽹络图，以及其源点和汇点，求出其⽹络最⼤流。
输⼊输出格式输⼊格式：第⼀⾏包含四个正整数N、M、S、T，分别表⽰点的个数、有向边的个数、源点序号、汇点序号。
接下来M⾏每⾏包含三个正整数ui、vi、wi，表⽰第i条有向边从ui出发，到达vi，边权为wi（即该边最⼤流量为wi）输出格式：⼀⾏，包含⼀个正整数，即为该⽹络的最⼤流。
输⼊输出样例输⼊样例#1：4 5 4 34 2 304 3 202 3 202 1 301 3 40输出样例#1：50说明时空限制：1000ms,128M数据规模：对于30%的数据：N<=10，M<=25对于70%的数据：N<=200，M<=1000对于100%的数据：N<=10000，M<=100000样例说明：题⽬中存在3条路径：4-->2-->3，该路线可通过20的流量4-->3，可通过20的流量4-->2-->1-->3，可通过10的流量（边4-->2之前已经耗费了20的流量）故流量总计20+20+10=50。
输出50。
求⽹络最⼤流的算法还是很多的，这⾥讲⼀下最简单的FF算法。
还是利⽤增⼴路，找到⼀条从源点到汇点的任意路径，所有边上的最⼩值delta如果不是0，那么总流量就可以增加delta，在将路径上的边的容量减去delta，这就是⼀条增⼴路。
易知，如果找不出增⼴路了，那么此时的流量就是最⼤了。
但是，就这样还不⾏，如果“⾛错了”怎么办？现在引进反向弧，反向弧可以解决这个问题。
其他的博客上很多说反向弧可以让流量后悔，这个⽐喻很⽣动，但⽤我⾃⼰的话来说，反向弧因为是同原边反向的，两者中⼀者减去delta时，将另⼀者加上delta，那么之后找增⼴路时，⾛反向弧相当于原边少⾛，⾮常巧妙。
算法⼤概是将完了，代码应该还好打的。
#include<set>#include<map>#include<queue>#include<cmath>#include<cstdio>#include<vector>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>#define INF 2147483647using namespace std;int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}struct edge{int next,to,head,b;}f[440000];long long ans;int tot=0,n,m,s,t;bool mark[400000]={0},flag;void add(int u,int v,int w){f[tot].next=f[u].head;f[u].head=tot;f[tot].to=v;f[tot].b=w;tot++;}int dfs(int x,int flow){//dfs求任意路径if(x==t){ans+=flow;flag=1;return flow;}mark[x]=1;for(int i=f[x].head;i!=-1;i=f[i].next){int x1=f[i].to;if(mark[x1]||f[i].b==0) continue;int delta=dfs(x1,min(flow,f[i].b));if(flag){f[i].b-=delta;f[i^1].b+=delta;return delta;}}return0;}void FF(){//有增⼴路就增⼴memset(mark,0,sizeof(mark));flag=0;dfs(s,INF);while(flag){memset(mark,0,sizeof(mark));flag=0;dfs(s,INF);}}int main(){n=read();m=read();s=read();t=read();for(int i=1;i<=n;++i) f[i].head=-1;while(m--){int x,y,w;x=read();y=read();w=read();add(x,y,w);add(y,x,0);}FF();printf("%lld",ans);return0;}注意，这种dfs的形式也是我⾃⼰很少打的，求任意⼀条路径，先dfs到汇点，再做⼀个标记flag，回来时有标记就更新。
