文化课 + 竞赛双废物又来水题解了。

首先，对于题干中的人，很像网络流中的流量，但是他有一个每天人数的下限，我从网上借鉴（chaoxi）到了两种思路：

1. 把下界限制转化为一条边的流量下界，这样就是最小费用上下界最大流。
2. 加入几个新值，其条件正好为 $\ge 0$，将其当做一条流量，这样不等式就变成了等式，我们可以利用流量守恒，用点的流满 $\Leftrightarrow $ 等式成立，这样就变成了一个最小费用最大流，去掉了上下界的影响。

其实这两种思路本质好像是一致的…

思路一

即 $y$ 总视频的解法，考虑到人的工作时间是一段区间，不妨差分考虑，先让 $i$ 的人无条件免费顺延到 $i + 1$ 的边，然后在 $S$ 和 $T$ 人为规定加入/去除即可，这样一类工作者只会设计常数的点边，复杂度正常。

那么建立网络 $G$：

• 对于一天 $i$，让 $i$ 点向 $i + 1$ 点连边。流量下界是 $A_i$、上界是正无穷，费用是 $0$，这条边的流量意味着第 $i$ 天的工作人数，
• 对于一类志愿者 $j$，让 $T_j + 1$ 向 $S_j$ 连一条容量无界限，费用是 $C_i$ 的边，这条边可以自由活动，意味着自由安排是志愿者。

这样，每个志愿者相当于在流网络的一单位的流量流过了一个环，这个问题变成了最小费用无源汇上下界可行流，我们都知道可行流的可行判定经过转化就是跑到最大流，所以转化完后用最小费用最大流就行了。

时间复杂度

$O(n^2m)$ 复杂度真棒

Code

这题 Acwing 咋这么卡常啊

#include <iostream>
#include <cstdio>
#include <cstring>
#define rint register int
typedef long long LL;

using namespace std;

const int N = 1005, M = (N * 2 + 10000) * 2, INF = 0x3f3f3f3f;

int n, m, a[N], incf[N], d[N], q[N], pre[N]; 
int head[N], numE = 1, S, T;
bool vis[N];
LL ans;
struct E{
    int next, v, w, c;
} e[M];

void inline add(int u, int v, int w, int c) {
    e[++numE] = (E) { head[u], v, w, c };
    head[u] = numE;
    e[++numE] = (E) { head[v], u, 0, -c };
    head[v] = numE;
}

bool inline spfa() {
    memset(d, 0x3f, sizeof d);
    rint hh = 0, tt = 1;
    d[S] = 0, q[0] = S, incf[S] = INF;
    while (hh != tt) {
        rint u = q[hh++]; vis[u] = false;
        if (hh == N) hh = 0;
        for (rint i = head[u]; i; i = e[i].next) {
            rint v = e[i].v;
            if (d[u] + e[i].c < d[v] && e[i].w) {
                d[v] = d[u] + e[i].c, pre[v] = i, incf[v] = min(incf[u], e[i].w);
                if (!vis[v]) {
                    vis[v] = true, q[tt++] = v;
                    if (tt == N) tt = 0;
                }
            }
        }
    }
    return d[T] != INF;
}

void inline update() {
    int x = T;
    while (x != S) {
        int i = pre[x];
        e[i].w -= incf[T], e[i ^ 1].w += incf[T]; 
        x = e[i ^ 1].v;
    }
    ans += (LL)d[T] * incf[T];
}

int main() {
    scanf("%d%d", &n, &m); 
    S = n + 2, T = n + 3;
    for (rint i = 1, A; i <= n; i++) {
        scanf("%d", &A);
        add(i, i + 1, INF, 0);
        a[i] -= A, a[i + 1] += A;
    }
    for (rint i = 1, s, t, c; i <= m; i++) {
        scanf("%d%d%d", &s, &t, &c);
        add(t + 1, s, INF, c);
    }
    for (rint i = 1; i <= n + 1; i++) {
        if (a[i] > 0) add(S, i, a[i], 0);
        else if (a[i] < 0) add(i, T, -a[i], 0);
    }
    while (spfa()) update();
    printf("%lld\n", ans);
    return 0;
}

思路二

设一些新的变量：

• $B_i (B_i \ge 0)$，表示第 $i$ 天实际招了 $A_i + B_i$ 人。

• $D_i (D_i \ge 0)$，表示实际上第 $i$ 类志愿者招了 $D_i$ 类人

这样我们就可以列出 $n$ 个等式，对于第 $i$ 个等式（针对第 $i$ 天的匹配情况）

$$A_i + B_i = \displaystyle \sum_{S_j \le i \le T_j} D_j$$

但是为了让每个变量在流网络中、在每个等式中都相等，所以我们得让每个变量至多出现在两个式子中，（如果出现在一个式子，就可以将其到源汇点的费用改了，这样就是费用对应上了，如果两个式子，可以从本该连向汇点的边直接连向本该从源点出的边，这样费用对应。这里本人实力还是非常菜，很可能讲了一些玄学的东西，求大佬们轻喷。）

由于每个 $j$ 影响的 $i$ 是连续的一段，所以我们可以将式子前后加入两个 $0 = 0$，然后将式子差分（这是一步等价变换）这样每个 $D_j, B_i$ 都恰好会出现在两个式子之中。

对于第 $i$ 个等式而言，差分后的式子：

$$-A_{i-1} - B_{i-1} + A_i + B_i = \displaystyle -\sum_{i-1=T_j}D_j+\sum_{i=S_j}D_j$$

我们把式子移项，让每一项都是正的：
$$A_i + B_i + \displaystyle\sum_{i-1=T_j} D_j = A_{i-1}+B_{i-1}+\sum_{i=S_j}D_j$$

这样，我们可以把等式看作一个点的流量守恒等式，等式左右两侧分别是流入该点/流出改点的流量，我们建立流网络：

• 对于常量 $A$，在左侧则连一条自虚拟源点出发，到 $i$ 点，流量为 $A_i$，无费用的边，右侧连到汇点，即对称的。
• 对于变量 $B$，从 $B_i$ 所在右侧等式的点向 $B_i$ 所在左侧的点，即 $i$ 连向 $i-1$，这条边流量无限，意味着自由选择的 $B$，而这条边 + 流量守恒保证了 $B_i$ 在两个式子中不变
• 对于变量 $D$ 同理，即 $S_j$ 连向 $T_j + 1$，流量无限，费用为 $C_j$ 的边。

这样，在流网络跑到的最大流 = 从 $S$ 出发所有容量（满足常量的强行限制） $\Leftrightarrow$ 差分等式成立 $\Leftrightarrow$ 原始等式成立 $\Leftrightarrow$ 一个满足条件的方案

所以，原问题最小费用 $\Leftrightarrow$ 最小费用最大流

时间复杂度

$O(n^2m)$

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#define rint register int
typedef long long LL;

using namespace std;

const int N = 1005, M = (N * 3 + 10000) * 2, INF = 0x3f3f3f3f;

int n, m, a[N], incf[N], d[N], q[N], pre[N]; 
int head[N], numE = 1, S, T;
bool vis[N];
LL ans;
struct E{
    int next, v, w, c;
} e[M];

void inline add(int u, int v, int w, int c) {
    e[++numE] = (E) { head[u], v, w, c };
    head[u] = numE;
    e[++numE] = (E) { head[v], u, 0, -c };
    head[v] = numE;
}

bool inline spfa() {
    memset(d, 0x3f, sizeof d);
    rint hh = 0, tt = 1;
    d[S] = 0, q[0] = S, incf[S] = INF;
    while (hh != tt) {
        rint u = q[hh++]; vis[u] = false;
        if (hh == N) hh = 0;
        for (rint i = head[u]; i; i = e[i].next) {
            rint v = e[i].v;
            if (d[u] + e[i].c < d[v] && e[i].w) {
                d[v] = d[u] + e[i].c, pre[v] = i, incf[v] = min(incf[u], e[i].w);
                if (!vis[v]) {
                    vis[v] = true;
                    q[tt++] = v;
                    if (tt == N) tt = 0;
                }
            }
        }
    }
    return d[T] != INF;
}

void inline update() {
    int x = T;
    while (x != S) {
        int i = pre[x];
        e[i].w -= incf[T], e[i ^ 1].w += incf[T]; 
        x = e[i ^ 1].v;
    }
    ans += (LL)d[T] * incf[T];
}

int main() {
    scanf("%d%d", &n, &m); 
    S = n + 2, T = n + 3;
    for (rint i = 1, A; i <= n; i++) {
        scanf("%d", &A);
        add(S, i, A, 0), add(i + 1, T, A, 0);
        add(i + 1, i, INF, 0);
    }
    for (rint i = 1, s, t, c; i <= m; i++) {
        scanf("%d%d%d", &s, &t, &c);
        add(s, t + 1, INF, c);
    }
    while (spfa()) update();
    printf("%lld\n", ans);
    return 0;
}