[BZOJ4017] [Noi2008]志愿者招募（单纯形法）

发表于 | 分类于 ， | 评论数： | 阅读次数：

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

学习了一个学长的博客，真的很棒：https://www.hrwhisper.me/introduction-to-simplex-algorithm/

首先这题一定是规划问题，我们根据题意列出优化方程。比如测试样例：

3 3
2 3 4
1 2 2
2 3 5
3 3 2

我们设第$i$类志愿者招$x_i$个，那么目标是：
$$
\min 2x_1+5x_2+2x_3
$$
需要满足：
$$
x_1\geq 2
$$

$$
x_1+x_2\geq 3
$$

$$
x_2+x_3\geq 4
$$

对于这类$\min (CX); s.t.\ AX\geq Y$的问题，其对偶问题是：
$$
\max (YX’);s.t.\ A^TX’\leq C
$$
然后就会发现这个形式跟输入的格式完全一致了。

PS：至于为什么这个问题的线性规划一定保证是整数解，因为我们构造的矩阵是全幺模矩阵，有人出现则是1，不出现则是0，由全幺模矩阵的一个定理：对于任何整数向量b，方程组A的所有基本解为整数向量的充分条件是A为幺模矩阵。所以我们可以使用单纯形法解决这个整数规划问题。

套下模版。。

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<bits/stdc++.h>
using namespace std;

namespace Simplex {
  // s.t. ax≤b
  // MAX cx
  const int maxn = 1010;
  const int maxm = 10010;
  const double eps = 1E-9;
  const double inf = 1E18;
  int n, m;
  double a[maxm][maxn], b[maxm], c[maxn], v;
  void pivot(int l,int e) {
    b[l] /= a[l][e];
    for(int j = 1; j <= n; j++) {
      if(j != e) a[l][j] /= a[l][e];
    }
    a[l][e] = 1 / a[l][e];
    
    for(int i = 1; i <= m; i++) {
      if(i != l && fabs(a[i][e]) > 0) {
        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 j = 1; j <= n; j++) {
      if(j != e) c[j] -= c[e] * a[l][j];
    }
    c[e] = -c[e] * a[l][e];
  }
  double simplex() {
    while(1) {
      int e = 0, l = 0;
      for(e = 1; e <= n; e++) {
        if(c[e] > eps) break;
      }
      if(e == n + 1) return v;
      double mn = inf;
      for(int i = 1; i <= m; i++) {
        if(a[i][e] > eps && mn > b[i] / a[i][e]) {
          mn = b[i] / a[i][e];
          l = i;
        }
      }
      if(mn == inf) return inf;
      pivot(l, e);
    }
  }
}

const int maxn = 1010;
const int maxm = 10100;
int n, m;
int a[maxn];
int s[maxm], f[maxm], c[maxm];

signed main() {
  // freopen("in", "r", stdin);
  // freopen("out", "w", stdout);
  while(~scanf("%d%d",&n,&m)) {
    Simplex::n = n, Simplex::m = m;
    for(int i = 1; i <= n; i++) {
      scanf("%d",&a[i]);
      Simplex::c[i] = a[i];
    }
    for(int i = 1; i <= m; i++) {
      scanf("%d%d%d",&s[i],&f[i],&c[i]);
      Simplex::b[i] = c[i];
      for(int j = s[i]; j <= f[i]; j++) {
        Simplex::a[i][j] = 1;
      }
    }
    printf("%d\n", (int)(Simplex::simplex()+0.5));
  }
  return 0;
}