费用流

算法描述：

对于 $n$ 个节点，$m$ 条边的流网络，可以在 $O(nm^2)$ 的时间复杂度内求出该流网络的 最小费用最大流（最大费用最大流）。

算法步骤：

用 while 循环不断判断残量网络中是否存在增广路径。

对于循环中：

1. 找到增广路径
2. 更新残量网络
3. 累加最大流量

循环结束，得出最大流。

注意： EK 算法原本是用于求最大流的，但是经过严格的证明之后，只需要将 EK 算法中找增广路径的 bfs 算法替换成 spfa 算法即可。如果要求最小费用最大流，就用 spfa 算法找最短增广路；如果要求最大费用最大流，就用 spfa 算法找最长增广路。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 5010, M = 100010, INF = 0x3f3f3f3f;

int n, m, S, T;
int h[N], e[M], f[M], w[M], ne[M], idx; //邻接表
//q[] 表示队列
//d[] 表示每个节点到源点的最短费用
//pre[] 表示每个节点的最短路的前驱边
//incf[] 表示源点能传到每个节点的最大流量
//st[] 表示 spfa 算法中的判重数组
int q[N], d[N], pre[N], incf[N];
bool st[N];

void add(int a, int b, int c, int d) //添加边
{
    e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx++;
}

bool spfa() //判断是否存在最短增广路
{
    //初始化
    int hh = 0, tt = 1;
    q[0] = S;

    memset(d, 0x3f, sizeof d);
    d[S] = 0;

    memset(incf, 0, sizeof incf);
    incf[S] = INF;

    while(hh != tt) //spfa
    {
        int t = q[hh++];
        if(hh == N) hh = 0;
        st[t] = false;

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(f[i] && d[j] > d[t] + w[i])
            {
                d[j] = d[t] + w[i];
                pre[j] = i;
                incf[j] = min(f[i], incf[t]);

                if(!st[j])
                {
                    q[tt++] = j;
                    if(tt == N) tt = 0;

                    st[j] = true;
                }
            }
        }
    }

    return incf[T] > 0;
}

void EK(int &flow, int &cost) //EK 算法求最小费用流
{
    flow = 0, cost = 0; //记录最大流、最小费用
    while(spfa()) //如果存在最短增广路
    {
        int t = incf[T]; //记录当前最短增广路的最大流量
        flow += t, cost += t * d[T]; //累加最大流和最小费用
        for(int i = T; i != S; i = e[pre[i] ^ 1]) //将这条增广路径删掉
        {
            f[pre[i]] -= t;
            f[pre[i] ^ 1] += t;
        }
    }
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &S, &T);

    memset(h, -1, sizeof h); //初始化邻接表

    while(m--)
    {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        add(a, b, c, d);
    }

    int flow, cost;
    EK(flow, cost);
    printf("%d %d\n", flow, cost);

    return 0;
}