问题描述：
网络流：一个连通的赋权有向图 G = (V、E、C)，其中 V 是该图的顶点集，E 是有向边(即弧)集，C 是弧上的容量。此外顶点集中包括一个起点和一个终点。网络上的流就是由起点流向终点的可行流，它有两个性质：① 每条边的流量不超过它的容量；② 除 s 和 t 的任意结点，流入 u 的流量等于流出 u 的流量。
最大流问题：找到从 s 到 t 的一条线路，使得总流量最大。
最小割问题：图中所有的割中，边权值和最小的割为最小割。
设 Ci 为网络 N 中一些弧的集合，若从 N 中删去 Ci 中的所有弧能使得从源点 s 到汇点 t 的路集为空集时，称 Ci 为 s 和 t 间的一个割。
❗算法描述❗：
首先想到的算法是，从 s 开始广度优先搜索所有能到达 t 的路径，然后找每条路径上权值最小的边，再进行其它操作，就能找到这张图的最大流。
这里引入一个概念，增广路 (Aumenting Path)是指从 s 到 t 的一条路径，流过这条路径，使得当前的流（可以到达 t 的流量）可以增加。那么求最大流问题可以转换为不断求解增广路的问题，并且，显然当图中不存在增广路时就达到了最大流。
所以，我们就可以利用广搜算法，从 s 不断往外广搜，通过权值 > 0 的边到达 t，找到每条路径上的最小值 min，并把该条路径上的所有边值都减去 min，直到再也找不到增广路，将所有的 min 值累加在一起就得到了最大流。
但是，上述方法真的能得到最大流吗？不免会出现差错：一些流量已经到了某个节点，但由于下一条边的容量已经被占满，可用容量为 0，它们便不能继续通过。这时候呢，应该让这些流量返回走另一条路径，但上述算法不能实现这一功能。
因此，引入反向边。每次确定一条路径后，在剩余网络上加入对应的反向边，意思是，已经流过的流量可以“反悔”，重新回去找其他的路径通过。
这里补充一个概念：残量图 Residual Graph，它显示可用的容量的多少。在选定当前流后，减少了 G 的每条边的容量，并加入了对应的反向边。
所以，我们得到了一个解决最大流的直接算法。该算法采用迭代的方式进行，每次先构造一个 Gf，然后利用线性时间的广度优先搜索在 Gf 上找到 s 到 t 的一条可行的增广路径，找不到任何这样的路径时算法停止?。
❗算法实现❗：
（转载）
/* * * * * * * * C++ program for implementation of Ford Fulkerson algorithm * * * * * * * * */ #include <iostream> #include <limits.h> #include <string.h> #include <queue> using namespace std; // Number of vertices in given graph #define V 6 /* Returns true if there is a path from source 's' to sink 't' in residual graph. Also fills parent[] to store the path */ bool bfs(int rGraph[V][V], int s, int t, int parent[]) { // Create a visited array and mark all vertices as not visited bool visited[V]; memset(visited, 0, sizeof(visited)); // Create a queue, enqueue source vertex and mark source vertex as visited queue<int> q; q.push(s); visited[s] = true; parent[s] = -1; // Standard BFS Loop int u; while (!q.empty()) { // edge: u -> v u = q.front(); // head point u q.pop(); for (int v = 0; v < V; ++v) // tail point v { if (!visited[v] && rGraph[u][v] > 0) // find one linked vertex { q.push(v); parent[v] = u; // find pre point visited[v] = true; } } } // If we reached sink in BFS starting from source, then return true, else false return visited[t] == true; } // Returns the maximum flow from s to t in the given graph int fordFulkerson(int graph[V][V], int s, int t) { int u, v; int rGraph[V][V]; for (u = 0; u < V; ++u) { for (v = 0; v < V; ++v) { rGraph[u][v] = graph[u][v]; } } int parent[V]; int max_flow = 0; // Augment the flow while tere is path from source to sink while (bfs(rGraph, s, t, parent)) { // edge: u -> v int path_flow = INT_MAX; for (v = t; v != s; v = parent[v]) { // find the minimum flow u = parent[v]; path_flow = min(path_flow, rGraph[u][v]); } // update residual capacities of the edges and reverse edges along the path for (v = t; v != s; v = parent[v]) { u = parent[v]; rGraph[u][v] -= path_flow; rGraph[v][u] += path_flow; // assuming v->u weight is add path_flow } // Add path flow to overall flow max_flow += path_flow; } return max_flow; } int main() { int graph[V][V] = { {0,16,13, 0, 0, 0}, {0, 0,10,12, 0, 0}, {0, 4, 0, 0,14, 0}, {0, 0, 9, 0, 0,20}, {0, 0, 0, 7, 0, 4}, {0, 0, 0, 0, 0, 0} }; cout << "the maximum flow from v0 to v5 is:" << endl << fordFulkerson(graph, 0, 5); return 0; }（教你彻底理解）网络流：基本概念与算法 最大流最小割
最大流问题与Ford-Fulkerson算法介绍
按自己的习惯，将上述代码改动：
#include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; int vexnum, edgenum; vector<vector<int>> residual; int source, target; vector<int> parent; int fordFulkerson(); bool bfs(); int main() { cout << "请输入顶点数量、边数量:" << endl; cin >> vexnum >> edgenum; residual.resize(vexnum, vector<int>(vexnum, 0)); cout << "输入各边的顶点序号、容量:" << endl; for (int i = 0; i < edgenum; ++i) { int tmp1, tmp2, temp; cin >> tmp1 >> tmp2 >> temp; residual[tmp1][tmp2] = temp; } cout << "请输入源点、汇点的序号:" << endl; cin >> source >> target; cout << "最大流量: " << fordFulkerson() << endl; return 0; } int fordFulkerson() { // 存储每个顶点的父结点 parent.resize(vexnum); int maxflow = 0; while (bfs()) { int path_flow = INT_MAX; // 找到一条路径中的可流流量 for (int i = target; i != source; i = parent[i]) { path_flow = min(path_flow, residual[parent[i]][i]); } // 更新残量图 for (int i = target; i != source; i = parent[i]) { residual[parent[i]][i] -= path_flow; //正向边减path_flow residual[i][parent[i]] += path_flow; //反向边加path_flow } maxflow += path_flow; } return maxflow; } bool bfs() { vector<bool> visited(vexnum, false); queue<int> q; q.push(source); visited[source] = true; parent[source] = -1; // 广度优先搜索 while (!q.empty()) { int u = q.front(); q.pop(); for (int v = 0; v < vexnum; ++v) { if (!visited[v] && residual[u][v] > 0) { q.push(v); parent[v] = u; visited[v] = true; } } } return (visited[target] == true); }检验：
