网上的版本大都是java实现的，如最出名的图的匹配问题与最大流问题（三）——最大流问题Ford-Fulkerson方法Java实本文提供一种极简化的C++实现。关于最大流问题的知识请移步最大流问题-Ford-Fulkerson算法 或者Ford–Fulkerson algorithm，里浏览量最多那篇反正我是没看懂，就算是我懂最大流问题的Ford-Fulkerson解法，我还是被作者搞晕了。不过配图和排版还是挺不错的。不讲原理了，直接给代码：

CODE

#include<stdio.h> #include<stdlib.h> #include<vector> #include<algorithm> #define MAXVEX 100 #define INF 65535 //用于表示边的结构体 struct edge { int to;//终点 int cap;//容量 int rev;//反向边 }; std::vector<edge>G[MAXVEX];//图的邻接表表示 bool used[MAXVEX];//DFS中用到的访问标记 //向图中增加一条从s到t容量为cap的边 void addEdge(int from, int to, int cap) { edge e; e.cap = cap;e.to = to;e.rev = G[to].size(); G[from].push_back(e); e.to = from; e.cap = 0; e.rev = G[from].size() - 1; G[to].push_back(e); } //通过DFS寻找增广路 int dfs(int v, int t, int f) { if (v == t)return f; used[v] = true; for (int i = 0; i < G[v].size(); ++i) { edge &e = G[v][i]; if (!used[e.to] && e.cap > 0) { int d = dfs(e.to, t, std::min(f, e.cap)); if (d > 0){ e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } //求解从s到t的最大流 int max_flow(int s, int t) { int flow = 0; for (;;) { memset(used, 0, sizeof(used)); int f = dfs(s, t, INF); if (f == 0)return flow; flow += f; } }