BZOJ1061【NOI2008】志愿者招募 <线性规划转费用流>

Posted on 2018-04-25 Symbols count in article: 1.4k Reading time ≈ 5 mins.

Problem

【NOI2008】志愿者招募

$\mathrm{Time\;Limit:\;20\;Sec}$
$\mathrm{Memory\;Limit:\;162\;MB}$

Description

申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。
经过估算，这个项目需要 $N$ 天才能完成，其中第 $i$ 天至少需要 $A_i$ 个人。布布通过了解得知，一共有 $M$ 类志愿者可以招募。其中第 $i$ 类可以从第 $S_i$ 天工作到第 $T_i$ 天，招募费用是每人 $C_i$ 元。
新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。

Input

第一行包含两个整数 $N,M$ ，表示完成项目的天数和可以招募的志愿者的种类。
接下来的一行中包含 $N$ 个非负整数，表示每天至少需要的志愿者人数。
接下来的 $M$ 行中每行包含三个整数 $S_i,T_i,C_i$ ，含义如上文所述。
为了方便起见，我们可以认为每类志愿者的数量都是无限多的。

Output

仅包含一个整数，表示你所设计的最优方案的总费用。

Sample Input

Sample Output

HINT

$1\le N\le1000$ ， $1\le M\le10000$ ，题目中其他所涉及的数据均不超过 $2^{31}-1$ 。

标签：线性规划 费用流

Solution

经典线性规划转网络流。

由题意可知，共会有 $N$ 个限制条件，还有一个需要最小化的表达式。以样例作例子，第 $i$ 种招募 $x_i$ 人，则有

\begin{aligned} x_1&\ge2\\ x_2+x_3&\ge3\\ x_2+x_3&\ge4\\ we\;need\;to\;minimize\;&2x_1+5x_2+2x_3\\ \end{aligned}

接着设三个辅助变量 $y_1,y_2,y_3\;(y_1,y_2,y_3\ge0)$ ，使得

\begin{aligned} x_1-y_1&=2\\ x_2+x_3-y_2&=3\\ x_2+x_3-y_3&=4\\ \end{aligned}

在最前面和最后面加入两个 $0=0$ ，差分一下，得到

\begin{aligned} x_1-y_1-2&=0\\ x_2+x_3-y_2-x_1+y_1-1&=0\\ y_2-y_3-1&=0\\ -x_2-x_3+y_3+4&=0\\ \end{aligned}

发现每个变量只出现两次，并且正、负各一次。这个性质其实一定成立。因为每种志愿者只在一个区间内出现，即每个变量只会在连续的式子中出现，这样差分后就会只剩一次正和一次负。辅助变量也有这个性质是显然的。
如果将每个式子看成一个结点，等式可以看作这个点的流量平衡方程。将正看成出流，负看成入流，即可构图。例如，对于 $x_2$ ，其在第二个式子中出现正，在第四个式子中出现负，可以想成是从二号结点流出的 $x_2$ 流量进入四号结点。对于辅助变量也是一样。而对于每个式子中的常数项，可以看成从源点流出或流入汇点，即若移到左边后为负，则为从源点流出这么多流量；若为正，则为向汇点流这么多流量。
这样一来，根据费用流一定跑出最大流（废话），跑出的流一定满足流量平衡方程（废话$\times$2），最后跑出的方案一定能满足所有限制。如果加上边权（即所要取最小值的式子的系数），可以跑最小费用最大流解出最小值。

建模：

对于 $\forall i\in[1,n+1]$ $\forall i \in [1, n + 1]$ ，
- 若 $A_i\ge A_{i-1}$ ，连接 $S\to i$ ，容量 $A_i-A_{i-1}$ ，单位费用 $0$
- 若 $A_i<A_{i-1}$ ，连接 $i\to T$ ，容量 $A_{i-1}-A_i$ ，单位费用 $0$
对于一种志愿者 $l,r,w$ ，连接 $l\to r+1$ ，容量 $\infty$ ，单位费用 $w$
辅助变量：对于 $\forall i\in[2,n+1]$ ，连接 $i\to i-1$ ，容量 $\infty$ ，单位费用 $0$

跑最小费用最大流即可。

Code

#include <bits/stdc++.h>
#define MAX_N 2000
#define MAX_M 50000
#define INF 0x3f3f3f3f
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, s, t, cnt, pr[MAX_N+5], cr[MAX_N+5], mxf, mic;
struct node {int v, c, w, nxt;} E[MAX_M+5]; int a[MAX_N+5];
void init() {s = 0, t = n+2, cnt = 0, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c, int w) {E[cnt] = (node){v, c, w, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c, int w) {insert(u, v, c, w), insert(v, u, 0, -w);}
bool SPFA() {
    queue <int> que; bool inq[MAX_N+5]; int d[MAX_N+5], cr[MAX_N+5];
    memset(inq, false, sizeof inq), memset(d, INF, sizeof d);
    d[s] = 0, que.push(s), inq[s] = true, memset(cr, -1, sizeof cr);
    while (!que.empty()) {
        int u = que.front(); que.pop(), inq[u] = false;
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c, w = E[i].w;
            if (c && d[u]+w < d[v]) {
                d[v] = d[u]+w, cr[v] = i;
                if (!inq[v]) que.push(v), inq[v] = true;
            }
        }
    }
    if (d[t] == INF) return false;	int flow = INF;
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) flow = min(flow, E[i].c);
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) E[i].c -= flow, E[i^1].c += flow;
    mxf += flow, mic += d[t]*flow;	return true;
}
int main() {
    read(n), read(m), init();
    for (int i = 1; i <= n; i++) read(a[i]);
    for (int i = 1; i <= n+1; i++)
        if (a[i] >= a[i-1]) addedge(s, i, a[i]-a[i-1], 0);
        else addedge(i, t, a[i-1]-a[i], 0);
    for (int i = 1, u, v, w; i <= m; i++)
        read(u), read(v), read(w), addedge(u, v+1, INF, w);
    for (int i = 2; i <= n+1; i++) addedge(i, i-1, INF, 0);
    while (SPFA()) ;	return printf("%d\n", mic), 0;
}