ford-fulkerson算法c++

Ford-Fulkerson算法是解决最大流问题的一个基本算法。下面是使用C语言实现Ford-Fulkerson算法的伪代码：

// 定义一个结构体表示边
struct Edge {
    int from, to, capacity, flow;
};

// 确定起点和终点，以及图中所有的边
int s, t; // 起点和终点
vector<Edge> edges; // 所有的边

// 记录每个节点的出边，以及记录每个节点是否被访问过
vector<int> G[MAX_NODE]; // 最大节点数
bool visited[MAX_NODE]; // 最大节点数

// 添加一条从from到to的容量为capacity的边
void addEdge(int from, int to, int capacity) {
    edges.push_back((Edge){from, to, capacity, 0});
    edges.push_back((Edge){to, from, 0, 0});
    int m = edges.size();
    G[from].push_back(m-2);
    G[to].push_back(m-1);
}

// 找到从x到t的一条增广路，并返回增广路上的最小容量
int dfs(int x, int flow) {
    if (x == t) return flow;
    visited[x] = true;
    for (int i = 0; i < G[x].size(); i++) {
        Edge& e = edges[G[x][i]];
        if (!visited[e.to] && e.capacity > e.flow) {
            int d = dfs(e.to, min(flow, e.capacity - e.flow));
            if (d > 0) {
                e.flow += d;
                edges[G[x][i]^1].flow -= d;
                return d;
            }
        }
    }
    return 0;
}

// 计算最大流
int maxFlow() {
    int flow = 0;
    while (true) {
        memset(visited, false, sizeof(visited));
        int d = dfs(s, INF); // INF表示正无穷，即一个很大的数
        if (d == 0) return flow;
        flow += d;
    }
}

其中，`addEdge`函数用于添加一条从`from`到`to`的容量为`capacity`的边；`dfs`函数用于找到从`x`到`t`的一条增广路，并返回增广路上的最小容量；`maxFlow`函数用于计算最大流。