BZOJ1061 志愿者招募

  题意:一个项目有$n$天,第$i$天至少需要$A_i$个人。有$m$种志愿者可以招募,每一种可以从第$s_i$天工作到$t_i$天,费用每人$c_i$元。求用最少费用招募志愿者满足要求。

  这道题是经典的流量平衡模型。常用来解决一类特殊的线性规划问题。
  根据$n$天每天的供求关系,我们可以列出一系列不等式,最后求最大化一个线性式子。这正是线性规划。
  添加上松弛变量变为等式,等式间相减,发现每个变量正好在左边出现一次,在右边出现一次。
  这个时候我们就可以以等式为点,将符号为负的变量移到右边。等式左右表示入流量和出流量的平衡。假定左边为出流量,右边为入流量。每个变量由在左边的式子向在右边的式子连边,其中代表志愿者的边费用为$c_i$。将源点右边的常量连边,左边的常量与汇连边。跑一遍费用流,解决问题。
  存信息的数组又开小了,调了好久。。。明明可以在线直接把边加了的啊。。。

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
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for(int i = l, i##end = r; i <= i##end; ++i)
#define drep(i, l, r) for(int i = l, i##end = r; i >= i##end; --i)
#define erep(i, u) for(int i = head[u], v = to[i]; i; i = nxt[i], v = to[i])
#define ms(a, b) memset(a, b, sizeof a);
template<class T> inline bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template<class T> inline bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline T& read(T& x)
{
static char c; bool flag = 0;
while(!isdigit(c = getchar())) if(c == '-') flag = 1;
for(x = c - '0'; isdigit(c = getchar()); (x *= 10) += c - '0');
if(flag) x = -x; return x;
}
const int INF = 0x3f3f3f3f;
const int maxn = 1010, maxm = 15000;
int n, m;
int k[maxn];
int head[maxn], nxt[maxm << 1], to[maxm << 1], e = 1, c[maxm << 1], w[maxm << 1];
void ae(int x, int y, int C, int W)
{
to[++e] = y; nxt[e] = head[x]; head[x] = e;
c[e] = C; w[e] = W;
}
namespace MCMF
{
int S, T, p[maxn];
int dis[maxn], res[maxn], cost;
bool inq[maxn];
bool SPFA()
{
ms(dis, INF);
queue<int> q; q.push(S); inq[S] = 1;
dis[S] = p[S] = 0; res[S] = INF;
while(!q.empty())
{
int u = q.front(); q.pop(); inq[u] = 0;
erep(i, u) if(c[i] && chkmin(dis[v], dis[u] + w[i]))
{
res[v] = min(c[i], res[u]); p[v] = i;
if(!inq[v]) inq[v] = 1, q.push(v);
}
}
if(dis[T] == INF) return 0;
cost += dis[T] * res[T];
for(int u = T; u != S; u = to[p[u] ^ 1]) c[p[u]] -= res[T], c[p[u] ^ 1] += res[T];
return 1;
}
int maxflow(int s, int t)
{
S = s, T = t; cost = 0;
while(SPFA());
return cost;
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("exec.in", "r", stdin); freopen("exec.out", "w", stdout);
#endif
read(n); read(m); int s = 0, t = n + 2;
rep(i, 1, n) read(k[i]);
rep(i, 1, m)
{
int l, r, cost;
read(l), read(r), read(cost);
ae(l, r + 1, INF, cost), ae(r + 1, l, 0, -cost);
}
rep(i, 1, n + 1)
{
if(k[i] > k[i - 1]) ae(s, i, k[i] - k[i - 1], 0), ae(i, s, 0, 0);
if(k[i] < k[i - 1] ) ae(i, t, k[i - 1] - k[i], 0), ae(t, i, 0, 0);
}
rep(i, 2, n + 1) ae(i, i - 1, INF, 0), ae(i - 1, i, 0, 0);
printf("%d\n", MCMF::maxflow(s, t));
return 0;
}