餐巾计划问题

解题思路

本题要求我们每天都提供一定数量的毛巾，毛巾只有洗出来或者新买的才能在当天使用，洗毛巾可以快洗和慢洗，因此每一天的若干块毛巾只有三种来处，新买、快洗、慢洗，现在要求我们找到一种合理的毛巾使用方式让总花费最小。

新买需要 $p$，快洗需要 $f$，慢洗需要 $s$。

每天的毛巾有三种来处，新买、快洗、慢洗，也有三种去处，放着、快洗、慢洗，放着不洗是不能直接用的。

可以发现，每天我们都需要接收一些毛巾，也需要输出一些毛巾，如果把每一天看作一个节点，那么每个节点都会有两种操作，因此我们可以对每个点进行拆点操作。

将第 $i$ 天分成两个点，一个点 $i_1$ 表示用完的旧毛巾，一个点 $i_2$ 表示需要的新毛巾。

第 $i$ 天需要的新毛巾有三种来处，新买、快洗、慢洗。新买相当于凭空变出毛巾，从源点向 $i_2$ 连一条边，容量是 $+\infty$，费用是 $p$；快洗则是从第 $i - m$ 天的旧毛巾中洗出来的，因此从 $(i - m)_1$ 向 $i_2$ 连一条边，容量是 $+\infty$，费用是 $f$；慢洗则是从第 $i - n$ 天的旧毛巾中洗出来的，因此从 $(i - n)_1$ 向 $i_2$ 连一条边，容量是 $+\infty$，费用是 $s$。本题中第 $i$ 天固定只需要 $r_i$ 条毛巾，因此从 $i_2$ 向汇点连一条容量是 $r_i$ 的边，费用是 $0$。

第 $i$ 天用完的毛巾也有三种去处，留着、快洗、慢洗。留着相当于将第 $i$ 天的旧毛巾放到了第 $i + 1$ 天，因此从 $i_1$ 向 $(i + 1)_1$ 连一条边，容量是 $+\infty$，费用是 $0$；快洗则是将第 $i$ 天的旧毛巾洗了给第 $i + m$ 天，因此从 $i_1$ 向 $(i + m)_2$ 连一条边，容量是 $+\infty$，费用是 $f$；慢洗则是将第 $i$ 天的旧毛巾洗了给第 $i + n$ 天，因此从 $i_1$ 向 $(i + n)_2$ 连一条边，容量是 $+\infty$，费用是 $s$。第 $i$ 天还会产生 $r_i$ 条旧毛巾，因此从源点向 $i_1$ 连一条边，容量是 $r_i$，费用是 $0$。

通过以上方式就能构建出一个流网络，可以发现原问题中任意一个合理方案都能对应到流网络中任意一个可行流，并且由于到汇点的流量之和是 $\sum r_i$，所以任意一个合理方案对应到流网络中都是最大流。然后我们还能进一步发现原问题的任意一个方案的总费用和流网络中任意一个最大流的总费用是一一对应的，这里的结论可以自行证明。

综上所述，原问题的最小费用，就是流网络里所有最大流中费用最小的一个，即最小费用最大流。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1610, M = 9610, INF = 0x3f3f3f3f;

int n, p, x, xp, y, yp, 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])
        {
            f[pre[i]] -= t;
            f[pre[i] ^ 1] += t;
        }
    }
    return cost;
}

int main()
{
    scanf("%d%d%d%d%d%d", &n, &p, &x, &xp, &y, &yp);

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

    //第 i 天，用完的旧毛巾 编号为 i，需要的新毛巾 编号为 i + n
    S = 0, T = 2 * n + 1;
    for(int i = 1; i <= n; i++)
    {
        int r;
        scanf("%d", &r);

        add(S, i, r, 0); //每天会产出 r[i] 条旧毛巾
        add(n + i, T, r, 0); //每天需要 r[i] 条新毛巾
        add(S, n + i, INF, p); //每天可以购买若干条新毛巾，费用是 p
        if(i + 1 <= n) add(i, i + 1, INF, 0); //每天可以留若干条旧毛巾到下一天
        if(i + x <= n) add(i, n + i + x, INF, xp); //每天可以快洗若干条旧毛巾给 x 天后用，费用是 xp
        if(i + y <= n) add(i, n + i + y, INF, yp); //每天可以慢洗若干条旧毛巾给 y 天后用，费用是 yp
    }

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

    return 0;
}