志愿者招募问题

解题思路

本题有一个 $n$ 天的项目，每天至少需要 $a_i$ 个人，一共有 $m$ 类打工人，每类人能从第 $s_i$ 天工作到第 $t_i$ 天，且需要 $c_i$ 的费用，现在要求我们设计一个合理的方案让费用最小。

我们可以用一条边来表示一天，用 $1$ 到 $2$ 的边表示第 $1$ 天需要的人数，用 $2$ 到 $3$ 的边表示第 $2$ 天需要的人数，以此类推。

由于每天是至少需要 $a_i$ 个人，是可以大于 $a_i$ 的，相当于每条边都有一个下界的限制，并且本题还要求费用，因此本题是一个无源汇上下界可行费用流问题。

然后我们考虑如何在图中把志愿者表示出来，假设现在有一个志愿者可以从第 $2$ 天工作到第 $3$ 天，相当于可以从第 $2$ 天连续流过两条边，第 $4$ 天开始该志愿者就不能继续工作了，对于流网络来说相当于从点 $4$ 开始这段流量就消失了，但是我们要保证整个流网络是流量守恒的，所以我们可以从点 $4$ 向点 $2$ 连一条边，让点 $2$ 到点 $4$ 之间形成一个循环，保证该支援者在第 $3$ 天工作完之后将流量回流，保证流量守恒。通过这样的思路我们就可以表示所有类型的志愿者，并且每个志愿者对应的回流的那条边的流量就是该类志愿者的人数，因此这些回流边的容量就是 $+\infty$，费用是该类志愿者的费用。

通过以上分析，我们就能构建出一个无源汇有上下界的流网络 $G$，很容易可以证明流网络中任意一个可行流和原问题的任意一个可行方案都是一一对应的，并且两者的费用也是一一对应的，可以自行证明。

综上所述，我们要想求原问题的最小费用，只需要求流网络中的无源汇上下界最小费用可行流，这里需要参考 无源汇上下界可行流问题 的解法来做。然后我们就能根据 $G$ 构建出 $G’$，并且 $G$ 中任意一个可行流和 $G’$ 中任意一个满流都是一一对应的。我们要求 $G$ 中可行流的费用最小值，对应的要求 $G’$ 中满流的费用最小值，即 $G’$ 中的最小费用最大流。

注意： 并不是所有的费用流都可以和上下界可行流关联起来，因为本题中所有费用是没有下界的，所以对于原图的任何一个可行流 $f$，通过以上的对应方式对应到满流 $f’$，由于 $f$ 和 $f’$ 中有费用的边都是一样的，因此这两个流虽然不一样，但是费用是一样的，所以才可以关联起来。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010, M = 24010, INF = 0x3f3f3f3f;

int n, m, S, T;
int h[N], e[M], w[M], f[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", &n, &m);

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

    S = 0, T = n + 2; //源点、汇点
    //由于每个点只有一条入边一条出边，入边下界就是前一天的人数，出边下界就是当天的人数
    int last = 0; //记录前一天的人数（入边下界）
    for(int i = 1; i <= n; i++)
    {
        int cur; //记录当天的人数（出边下界）
        scanf("%d", &cur);

        if(last > cur) add(S, i, last - cur, 0); //C入 > C出
        else if(last < cur) add(i, T, cur - last, 0); //C出 > C入

        add(i, i + 1, INF - cur, 0); //从每个点向下一个点连边（即该点的出边），容量为 INF - cur（下界），费用是 0

        last = cur; //更新前一天的人数
    }
    add(S, n + 1, last, 0); //点 n + 1 一定是入边是第 n 天的人数，出边是 0

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

        add(b + 1, a, INF, c); //从 b + 1 向 a 连边，容量是 INF，费用是该志愿者的费用
    }

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

    return 0;
}