题解：运输问题

一、题目分析

本题中(W)公司有(m)个仓库和(n)个零售商店，每个仓库有一定数量的货物，每个零售商店有相应的货物需求，且货物供需平衡。同时，从每个仓库运送单位货物到每个零售商店有对应的费用，要求设计一个将仓库中所有货物运送到零售商店的最优运输方案，并计算出最小运输费用。

二、解题思路

本题通过构建网络流模型，利用费用流算法（基于EK算法的费用流实现）来求解最优运输方案和最小费用。具体思路如下：

（一）构建网络流图

1. 节点设置：定义超级源点(S = 0)和超级汇点(T = m + n + 1)。将(m)个仓库编号为(1)到(m)，(n)个零售商店编号为(m + 1)到(m + n)。
2. 边的设置：
   • 从超级源点(S)向每个仓库节点(i)连一条边，容量为仓库(i)的货物数量(a_i)，费用为(0)，表示货物从源点流入仓库。
   • 从每个零售商店节点(m + j)向超级汇点(T)连一条边，容量为零售商店(j)的货物需求量(b_j)，费用为(0)，表示货物从零售商店流入汇点。
   • 从每个仓库节点(i)向每个零售商店节点(m + j)连一条边，容量设为无穷大(INF)，费用为从仓库(i)运送单位货物到零售商店(j)的费用(c_{ij})，表示仓库和零售商店之间的运输路径及费用。

（二）费用流算法求解

1. 添加边函数add：用于在邻接表中添加边，对于每条从(a)到(b)，容量为(c)，费用为(d)的边，同时添加反向边（反向边容量为(0)，费用为(-d)），以便在增广路径时处理流量的退还和费用的计算。
2. 寻找增广路径（spfa函数）：使用spfa算法（这里用于寻找费用最小的增广路径），初始化距离数组d（设为无穷大）和最小剩余容量数组incf（设为(0)），将源点加入队列，距离设为(0)，最小剩余容量设为无穷大。在队列不为空时，遍历节点的邻接边，若边有剩余容量且通过该边到达邻接点的费用更小，则更新邻接点的距离、前驱边和最小剩余容量，若邻接点不在队列中则加入队列。当队列为空时，若汇点的最小剩余容量大于(0)，说明找到了增广路径，返回true；否则返回false。
3. 更新流量与费用（EK函数）：当找到增广路径后，获取汇点的最小剩余容量(t)，更新总费用（费用累加(t * d[T])），并沿着增广路径更新边的容量（正向边减去(t)，反向边加上(t)）。不断重复寻找增广路径和更新的过程，直到不存在增广路径，此时得到的总费用即为最小运输费用。

（三）输出最优运输方案

在第一次调用EK函数得到最小费用后，对边的容量和费用进行调整（正向边和反向边的容量相加，费用取相反数），再次调用EK函数，此时返回的结果可以用于输出具体的运输方案（这里代码中只是简单输出了一个值，实际应用中可根据调整后的边容量获取各仓库到零售商店的具体运输量）。

三、代码实现细节

（一）头文件与全局变量

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

using namespace std;

const int N = 160, M = 5150 * 2 + 10, 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 ++ ;
}

该函数用于在邻接表中添加一条边及其反向边，设置正向边和反向边的终点、容量和费用。

（三）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(incf[t], f[i]);
                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函数

int EK()
{
    int cost = 0;
    while (spfa())
    {
        int t = incf[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;
        }
    }
    return cost;
}

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

（五）main函数

int main()
{
    scanf("%d%d", &m, &n);
    S = 0, T = m + n + 1;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i ++ )
    {
        int a;
        scanf("%d", &a);
        add(S, i, a, 0);
    }
    for (int i = 1; i <= n; i ++ )
    {
        int b;
        scanf("%d", &b);
        add(m + i, T, b, 0);
    }
    for (int i = 1; i <= m; i ++ )
        for (int j = 1; j <= n; j ++ )
        {
            int c;
            scanf("%d", &c);
            add(i, m + j, INF, c);
        }

    printf("%d\n", EK());

    for (int i = 0; i < idx; i += 2)
    {
        f[i] += f[i ^ 1], f[i ^ 1] = 0;
        w[i] = -w[i], w[i ^ 1] = -w[i ^ 1];
    }
    printf("%d\n", -EK());

    return 0;
}

• 读取仓库数(m)和零售商店数(n)，设置超级源点(S = 0)，超级汇点(T = m + n + 1)，初始化邻接表（将(h)数组设为(-1)）。
• 读取每个仓库的货物数量，从超级源点向仓库连边。
• 读取每个零售商店的货物需求量，从零售商店向超级汇点连边。
• 读取仓库到零售商店的运输费用，在仓库和零售商店之间连边。
• 调用EK函数，输出最小运输费用。
• 调整边的容量和费用（正向边和反向边容量相加，费用取相反数）。
• 再次调用EK函数（这里输出的值可用于进一步获取运输方案），程序结束。

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

（一）时间复杂度

• 建图阶段：读取输入并构建邻接表，时间复杂度为(O(mn + m + n))。
• 费用流算法阶段：每次spfa寻找增广路径的时间复杂度在最坏情况下为(O((m + n)^2))，而基于spfa的费用流算法最多执行(O((m + n) \times \max(a_i, b_j)))次增广（(\max(a_i, b_j))表示最大的仓库货物量或零售商店需求量）。所以总的时间复杂度为(O((m + n)^2 \times (m + n) \times \max(a_i, b_j)))。

（二）空间复杂度

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