运输问题

解题思路

本题有 $m$ 个仓库和 $n$ 个零售店，每个仓库中都有一定数量的货物，而每个零售店需要一定数量的货物，这里保证所有仓库中的货物和所有零售店需要的货物数量是相等的。

从每个仓库将货物运送到每个零售店都需要不同的费用。然后我们要求将所有仓库的货物合理运输到所有零售店中需要的最小花费。

可以发现本题是费用流的直接应用，我们可以直观的去考虑流网络的建图方式。我们把货物看成从仓库流向零售店，那么如果将仓库看作源点，零售店看作汇点，这就是一个多源多汇的网络流问题。

对于这类问题，我们可以建立一个虚拟源点，向每个仓库连一条边，这样就能保证流网络只有一个源点，边的容量就是每个仓库中的货物数量，费用是 $0$，因为货物最开始就在仓库中，因此流向仓库是不需要花费的。同理，再建立一个虚拟汇点，从每个零售店向虚拟汇点连一条边，边的容量就是每个零售店需要的货物数量，费用也是 $0$，因为货物运到零售店就可以了，再流向虚拟汇点一样不需要花费。

每个仓库都可以向每个零售店运货，因此从每个仓库向每个零售店连一条边，由于运送货物的数量没有限制，所以容量都是 $+\infty$，费用就是题目给定的值，假设从第 $i$ 个仓库向第 $j$ 个零售店运送货物，费用就是 $c_{ij}$。

很直观的就可以发现，我们构建的流网络中任意一个最大可行流和原问题的任意一个运输方案都是一一对应的，然后原问题要求让运输方案的费用最小，流网络中只有中间的边有费用，因此我们需要再看一下最大可行流中间边的费用和运输方案的费用是否相等。费用等于每条边的流量乘上费用，对应到原问题的方案中就等价于每对仓库和零售店之间运输的货物数量乘以单价，因此在费用上也是一一对应的。

综上所述，我们要想求原问题的运输方案的最小花费，只需要求我们构建的流网络的最小费用最大流。

本题还要求原问题的运输方案的最大花费，对应的就是流网络的最大费用最大流，一种方法是再在 EK 算法中用 spfa 求最长增广路，我们也可以将所有边的费用取反，这样原图的最大费用最大流就等价于新图的最小费用最大流，然后再将求出的费用取反回来就是运输方案的最大花费。

这里有一个小细节，spfa 不能处理负权回路，有负权并没有关系，本题建图不可能存在负权回路，并且残量网络中虽然有反向边，但是走过去再走回来等于没走，因此 spfa 是可以正常运行的

注意： 本题所有货物运输的数量肯定是整数，因此我们求的其实是整数型最小费用最大流，而 EK 算法其实求的是所有流的最小费用最大流，但是由于算法过程中我们都是用的整数类型变量，因此保证我们最终求出来的一定是整数型的最小费用最大流。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 160, M = 10310, INF = 0x3f3f3f3f;

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]; //EK 算法需要的数组
bool st[N]; //spfa 算法中的判重数组

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)
    {
        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(incf[t], f[i]);

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

    return incf[T] > 0;
}

int EK() //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])
        {
            int j = e[i];
            f[pre[i]] -= t;
            f[pre[i] ^ 1] += t;
        }
    }
    return cost;
}

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

    memset(h, -1, sizeof h);

    //仓库编号 1 ~ n，零售店编号 n + 1 ~ n + m
    S = 0, T = n + m + 1; //源点、汇点
    for(int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        add(S, i, x, 0); //从源点向所有仓库连一条边，容量是存储的货物数量，费用是 0
    }
    for(int i = 1; i <= m; i++)
    {
        int x;
        scanf("%d", &x);
        add(n + i, T, x, 0); //从所有零售店向汇点连一条边，容量是需要的货物数量，费用是 0
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            int x;
            scanf("%d", &x);
            add(i, n + j, INF, x); //从所有仓库向所有零售店连一条边，容量是 INF，费用是对应花费
        }

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