lingo求最小费用最大流问题的代码

以下是一个使用Edmonds-Karp算法求解最小费用最大流问题的C++代码，其中`n`表示节点数目，`m`表示边数目，`s`表示源点，`t`表示汇点，`u[i]`和`v[i]`表示第`i`条边的起点和终点，`w[i]`表示第`i`条边的费用，`c[i]`表示第`i`条边的容量，`h[i]`表示第`i`个节点的高度，`e[i]`表示从源点到第`i`个节点的残量，`f[i][j]`表示第`i`个节点到第`j`个节点的流量，`d[i]`表示从源点到第`i`个节点的最短路长度，`p[i]`表示从源点到第`i`个节点的最短路中的上一条边的编号。

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const int maxn = 1e5 + 5;
int n, m, s, t;
int u[maxn], v[maxn], w[maxn], c[maxn];
int h[maxn], e[maxn], f[maxn][maxn];
int d[maxn], p[maxn];
bool vis[maxn];

void add_edge(int x, int y, int z, int cost) {
    u[++m] = x, v[m] = y, w[m] = cost, c[m] = z;
}

bool spfa() {
    fill(d + 1, d + n + 1, inf);
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    q.push(s);
    d[s] = 0, vis[s] = 1;
    e[s] = inf;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for (int i = 1; i <= m; i++) {
            int y = v[i];
            if (c[i] && d[x] + w[i] < d[y]) {
                d[y] = d[x] + w[i];
                e[y] = min(e[x], c[i]);
                p[y] = i;
                if (!vis[y]) {
                    vis[y] = 1;
                    q.push(y);
                }
            }
        }
    }
    return d[t] != inf;
}

int mcmf() {
    int maxflow = 0, mincost = 0;
    while (spfa()) {
        int flow = e[t];
        maxflow += flow;
        mincost += flow * d[t];
        for (int x = t; x != s; x = u[p[x]]) {
            c[p[x]] -= flow;
            c[p[x] ^ 1] += flow;
            f[u[p[x]]][x] += flow;
            f[x][u[p[x]]] -= flow;
        }
    }
    return mincost;
}

其中`add_edge`函数用于添加一条从`x`到`y`的容量为`z`，费用为`cost`的边，因为每条边都要建立反向边，所以实际上会添加两条边。

这个算法的时间复杂度为$O(fm\log n)$，其中$f$表示最大流量，$m$表示边数目，$n$表示节点数目，但是实际运行效率很高。