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;
}