C++实现最大网络流算法

下面是一个基于Ford-Fulkerson算法的最大网络流算法的C++实现，其中使用了BFS来寻找增广路径：

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 1005;
const int INF = 0x3f3f3f3f;

int n, m, s, t; // 网络中节点和边的数量，源节点和汇节点
int graph[MAXN][MAXN], parent[MAXN];

// 寻找增广路径
bool bfs() {
    memset(parent, -1, sizeof(parent));
    queue<int> q;
    q.push(s);
    parent[s] = -2;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v = 0; v < n; ++v) {
            if (parent[v] == -1 && graph[u][v]) {
                parent[v] = u;
                if (v == t) return true;
                q.push(v);
            }
        }
    }
    return false;
}

// 计算最大网络流
int max_flow() {
    int flow = 0;
    while (bfs()) {
        int path_flow = INF;
        for (int v = t; v != s; v = parent[v]) {
            int u = parent[v];
            path_flow = min(path_flow, graph[u][v]);
        }
        for (int v = t; v != s; v = parent[v]) {
            int u = parent[v];
            graph[u][v] -= path_flow;
            graph[v][u] += path_flow;
        }
        flow += path_flow;
    }
    return flow;
}

int main() {
    cin >> n >> m >> s >> t;
    memset(graph, 0, sizeof(graph));
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u][v] = w;
    }
    cout << "Max flow: " << max_flow() << endl;
    return 0;
}

其中，graph为网络的邻接矩阵表示，s为源节点的编号，t为汇节点的编号。函数max_flow()返回最大网络流的大小。

在实现中，使用了一个bfs()函数来寻找增广路径，其返回值为bool类型。在每次循环中，都会调用bfs()函数来查找增广路径，如果找到了增广路径，则计算这条路径上的最小流量，然后更新网络中的流量。重复这个过程直到无法找到增广路径，此时最大网络流的大小就是当前网络中的流量。