题解：费用流问题

一、题目分析

本题给定一个包含(n)个点和(m)条边的有向图，每条边都有对应的容量和费用。要求找出从源点(S)到汇点(T)的最大流，并且在流量达到最大的情况下，求出最小费用。

二、解题思路

本题采用费用流的经典算法——EK（Edmonds-Karp）费用流算法来求解。该算法基于增广路径的思想，在寻找增广路径时考虑边的费用，以确保在达到最大流的同时费用最小。

（一）图的存储与边的添加

使用邻接表来存储有向图。add函数用于添加边，对于每条从(a)到(b)，容量为(c)，费用为(d)的边，不仅添加正向边，还添加一条反向边。反向边的容量初始为(0)，费用为正向边费用的相反数，这是为了在增广路径时能够正确处理流量的退还和费用的计算。

（二）寻找增广路径

通过spfa（Shortest Path Faster Algorithm，这里用于寻找费用最小的增广路径）算法来寻找从源点(S)到汇点(T)的增广路径。在spfa过程中：
1. 初始化距离数组d，将所有点的距离设为无穷大，源点(S)的距离设为(0)。同时初始化incf数组，用于记录从源点到每个点的最小剩余容量。
2. 利用队列进行广度优先搜索，遍历每个点的所有邻接边。如果当前边还有剩余容量（(f[i]>0)），并且通过当前边到达邻接点的费用更小（(d[ver]>d[t]+w[i])），则更新邻接点的距离、前驱边、最小剩余容量。如果邻接点不在队列中，则将其加入队列。
3. 当队列为空时，若汇点(T)的最小剩余容量大于(0)，说明找到了增广路径，返回true；否则返回false，表示不存在增广路径。

（三）更新流量与费用

当找到增广路径后，通过EK函数进行流量和费用的更新：
1. 流量更新：flow累加汇点(T)的最小剩余容量incf[T]，这表示通过该增广路径增加的流量。
2. 费用更新：cost累加通过该增广路径传输流量所产生的费用，即incf[T]*d[T]。
3. 边的容量更新：沿着增广路径，正向边的容量减去incf[T]，反向边的容量加上incf[T]，以反映流量在路径上的变化。

（四）重复寻找与更新

不断重复上述寻找增广路径和更新流量与费用的过程，直到不存在增广路径为止。此时得到的flow即为从源点(S)到汇点(T)的最大流，cost即为流量最大时的最小费用。

三、代码实现细节

（一）头文件与全局变量

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5010, M = 100010, INF = 1e8;

int n, m, S, T;
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];

• 引入输入输出、字符串操作和算法相关头文件，并使用标准命名空间。
• 定义常量(N)表示节点最大数量，(M)表示边的最大数量，(INF)表示无穷大。
• 定义变量(n)、(m)、(S)、(T)分别表示节点数、边数、源点和汇点。
• 定义数组(h[N])为邻接表头数组，(e[M])存储边的终点，(f[M])存储边的容量，(w[M])存储边的费用，(ne[M])存储同一起点下一条边的编号，(idx)用于记录边的编号。
• 定义数组(q[N])为spfa算法的队列，(d[N])记录从源点到各点的距离，(pre[N])记录前驱边，(incf[N])记录从源点到各点的最小剩余容量。
• 定义布尔数组(st[N])用于标记节点是否在队列中。

（二）添加边函数add

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 ++ ;
}

该函数用于在邻接表中添加一条边及其反向边。正向边的信息包括终点(b)、容量(c)、费用(d)；反向边的终点为(a)，容量初始为(0)，费用为(-d)。

（三）spfa函数

bool spfa()
{
    int hh = 0, tt = 1;
    memset(d, 0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    q[0] = S, d[S] = 0, incf[S] = INF;
    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if (f[i] && d[ver] > d[t] + w[i])
            {
                d[ver] = d[t] + w[i];
                pre[ver] = i;
                incf[ver] = min(f[i], incf[t]);
                if (!st[ver])
                {
                    q[tt ++ ] = ver;
                    if (tt == N) tt = 0;
                    st[ver] = true;
                }
            }
        }
    }

    return incf[T] > 0;
}

• 初始化队列的头指针(hh = 0)，尾指针(tt = 1)，将距离数组d初始化为无穷大，最小剩余容量数组incf初始化为(0)。将源点(S)加入队列，设置其距离为(0)，最小剩余容量为无穷大。
• 当队列不为空时，取出队头节点(t)，标记该节点不在队列中。遍历节点(t)的所有邻接边，如果边有剩余容量且通过该边到达邻接点的费用更小，则更新邻接点的距离、前驱边、最小剩余容量。若邻接点不在队列中，则将其加入队列并标记。
• 最后，若汇点(T)的最小剩余容量大于(0)，返回true，表示找到了增广路径；否则返回false。

（四）EK函数

void EK(int& flow, int& cost)
{
    flow = 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;
        }
    }
}

• 初始化流量flow和费用cost为(0)。
• 当存在增广路径时（spfa返回true），获取汇点(T)的最小剩余容量(t)，更新流量和费用。然后沿着增广路径更新边的容量，正向边减去(t)，反向边加上(t)。

（五）main函数

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;
}

• 读取节点数(n)、边数(m)、源点(S)和汇点(T)，初始化邻接表。
• 读取每条边的信息（起点(a)、终点(b)、容量(c)、费用(d)），调用add函数添加边。
• 调用EK函数计算最大流和最小费用，最后输出结果。

四、时间复杂度和空间复杂度

（一）时间复杂度

• 建图阶段：读取边信息并构建邻接表，时间复杂度为(O(m))。
• 寻找增广路径与更新阶段：每次spfa寻找增广路径的时间复杂度在最坏情况下为(O(nm))，而EK算法最多执行(O(mC))次增广（(C)是所有边的最大容量）。所以总的时间复杂度为(O(m^2nC))。在本题数据范围内，边的容量(c)最大为(100)，实际运行效率会相对较好。

（二）空间复杂度

主要空间消耗在存储图的邻接表以及辅助数组上。邻接表的空间复杂度为(O(m))，辅助数组（如队列、距离数组、前驱数组等）的空间复杂度为(O(n))。所以总的空间复杂度为(O(n + m))。