网络或者网络流是一种基本的数据结构，而最大流则是网络流上的基本问题。网络本质上是一个符合一定条件的有向带权图。而最大流是最大可行流的简称，可行流是一个定义在网络流上的符合一定条件的函数。这些定义条件对于算法的正确性是不可缺少的，不过本文不描述可行流的数学条件，只介绍最大流最常用的Ford-Fulkerson方法的原理。     如上左的权图称作容量网络，边权值表示该边的容量。

最大流问题的Ford-Fulkerson解法。可是说这是一种方法，而不是算法，因为它包含具有不同运行时间的几种实现。该方法依赖于三种重要思想：残留网络，增广路径和割。本文将会详细介绍这些内容，下一篇文章我们提供一种该方法的Java实现。 在介绍着三种概念之前，我们先简单介绍下Ford-Fulkerson方法的基本思想。首先需要了解的是Ford-Fulkerson是一种迭代的方法。

#include<iostream> #include<vector> using namespace std; #define INF 0x0fffffff #define min(a,b)(a<b?a:b) #define MAX_V 1000 struct edge {  int to,cap,rev; //指向to的反向边的标号  edge(){}  edge(int a,int b

背景 我们有图 G=(V, E)，V是顶点的集合，E是边的集合。图中边的权重都为非负数 （满足1，2两点有时称之为流网络）。对于这个图G，有两个顶点很重要，一个是源头s，一个是汇聚点t，我们想考虑的是从源头s流向汇聚点t的流。 我们想要解决的问题：在一个流里，有着每条边的运载能力限制，我最多能从源头运输多少数量到目的地。 那么什么是流呢？ 流的定义 定义：直观来说，流就像它的名字一样，从

文章目录 零、实验内容一、初探最大流问题二、解读论文评审问题(m=10,n=3)三、Ford-Fulkerson方法3.1 例子讲解（其中a>2,b>2）反向边得到论文分配方案 3.2 Ford-Fulkerson思维导图3.3 伪代码3.3.1 DFS寻找一条增广路径3.3.2 Ford-Fulkerson全流程 四、EK (Edmons-Karp)算法4.1 EK算法思维导图4.2 伪