[BZOJ 1061][NOI 2008] 志愿者招募

题目大意

给定 $n$ 天,第 $i$ 天需要 $a_i$ 个志愿者,有 $m$ 类志愿者,每类志愿者工作时间为 $[s_i, t_i]$,花费为 $c_i$,求最小花费。

$1 \leqslant n \leqslant 1,000$

$1 \leqslant m \leqslant 10,000$

题目链接

BZOJ 1061

CodeVS 1803

题解

单纯形裸题。用对偶原理转化。

有关单纯形算法见单纯型学习笔记

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <cstdio>
#include <cfloat>
#include <algorithm>
const int MAXN = 1005;
const int MAXM = 10005;
const double EPS = 1e-7;
struct LinearPlanning {
double A[MAXM][MAXN], b[MAXM], c[MAXN], v;
int n, m;
void pivot(int l, int e) {
b[l] /= A[l][e];
for (int i = 1; i <= n; i++) if (i != e) A[l][i] /= A[l][e];
A[l][e] = 1 / A[l][e];
for (int i = 1; i <= m; i++) {
if (i != l && abs(A[i][e]) > EPS) {
b[i] -= A[i][e] * b[l];
for (int j = 1; j <= n; j++) if (j != e) A[i][j] -= A[i][e] * A[l][j];
A[i][e] = -A[i][e] * A[l][e];
}
}
v += c[e] * b[l];
for (int i = 1; i <= n; i++) if (i != e) c[i] -= c[e] * A[l][i];
c[e] = -c[e] * A[l][e];
}
double operator()(int n, int m) {
this->n = n;
this->m = m;
while (true) {
int i;
for (i = 1; i <= n; i++) if (c[i] > EPS) break;
int e = i;
if (e == n + 1) return v;
double temp = DBL_MAX;
int l;
for (i = 1; i <= m; i++) if (A[i][e] > EPS && b[i] / A[i][e] < temp) temp = b[i] / A[i][e], l = i;
if (temp == DBL_MAX) return DBL_MAX;
pivot(l, e);
}
}
} lp;
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%lf", &lp.c[i]);
for (int i = 1; i <= m; i++) {
int s, t, c;
scanf("%d %d %d", &s, &t, &c);
for (int j = s; j <= t; j++) lp.A[i][j] = 1;
lp.b[i] = c;
}
printf("%d\n", (int) (lp(n, m) + 0.5));
return 0;
}