[BZOJ4977] 跳伞求生

由于这篇 blog 写下时,目前爆炸 OJ 正处于爆炸状态,这里附一个题目描述。

题目描述

小 Q 最近沉迷于《跳伞求生》游戏。他组建了一支由 \(n\) 名玩家(包括他自己)组成的战队,编号依次为 \(1\)\(n\)。这个游戏中,每局游戏开始时,所有玩家都会从飞机上跳伞,选择一个目的地降落,跳伞和降落的时间有早有晚。在某局游戏降落前,他们在空中观察发现地面上一共有 \(m\) 间房子,编号依次为 \(1\)\(m\)。其中每间房子恰好有一名敌人早于他们到达。小 Q 战队的第 \(i\) 名玩家拥有 \(a_i\) 发子弹,地面上第 \(i\) 间房子里的敌人拥有 \(b_i\) 发子弹,消灭他可以获得 \(c_i\) 点积分。每名玩家必须且只能选择一间房子降落,然后去消灭里面的敌人。若第 \(i\) 名玩家选择了第 \(j\) 间房子,如果 \(a_i>b_j\),那么他就可以消灭该敌人,获得 \(a_i-b_j+c_j\) 的团队奖励积分,否则他会被敌人消灭。为了防止团灭,小 Q 不允许多名玩家选择同一间房子,因此如果某位玩家毫无利用价值,你可以选择让他退出游戏。因为房子之间的距离过长,你可以认为每名玩家在降落之后不能再去消灭其它房间里的敌人。作为小 Q 战队的指挥,请制定一套最优的降落方案,使得最后获得的团队奖励总积分最大。

\(n, m \le 10^5\)

做法

建如下费用流图,求最大费用流。

例图
例图

其中数字标注的是费用。

假设刚开始源点出发的那些边不存在,依次加入那些边,每次加入一条边后更新最小费用流。

可以注意到增广过程中加入的反向边都是从左到右的,这样的边不会被用到。

所以我们不需要关心初始时不在费用流图上的边。每次加入一条边后有三种情况:

  1. 增广一条源到汇的简单路径
  2. 消掉一个包含加入的边的简单负环 (因为是负环一定经过汇,所以也就一定恰好经过两条与汇相邻的边)
  3. 不作更新

第一种相当于是把新加入的边对应的玩家和一个没有被匹配的房子匹配,第二种相当于是把一个已匹配的房子匹配的玩家改为新加入的边对应的玩家。

把所有人和房子排个序,从左到右处理,用堆维护一下哪个收益比较大,如果都是负的就不作更新,否则就选收益较大的更新即可。

时间复杂度 \(\mathcal O(n \log n)\)

代码

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,int> pi;

ll ans = 0;
const ll inf = 1e18;
const int maxn = 100010;

/* struct Heap {
priority_queue<pi> pq, d;
int mt() {
while (!d.empty() && pq.top() == d.top()) {
d.pop();
pq.pop();
}
}
pi top() {
mt();
if (pq.empty()) {
return pi(-inf, 0);
}
return pq.top();
}
void push(pi p) {
pq.push(p);
}
void del(pi p) {
d.push(p);
}
} H1, H2;*/

priority_queue<pi> H1, H2;

// H1 未匹配,H2 已匹配

int n, m, a[maxn], b[maxn], c[maxn];
pi p[maxn << 1];

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
p[i] = pi(a[i], i);
}
for (int i = 1; i <= m; i++) {
scanf("%d%d", &b[i], &c[i]);
p[n+i] = pi(b[i], i + n);
}
sort(p + 1, p + n + m + 1);
for (int i = 1; i <= n + m; i++) {
int t = p[i].second;
if (t <= n) {
ll v1 = -inf, v2 = -inf;
pi p1 = H1.empty() ? pi(-inf, 0) : H1.top(), p2 = H2.empty() ? pi(-inf, 0) : H2.top();
v1 = p1.first + p[i].first, v2 = p2.first + p[i].first;
if (max(v1, v2) > 0) {
if (v1 > v2) {
H1.pop();
ans += v1;
H2.push(pi(-p[i].first, p1.second));
} else {
H2.pop();
ans += v2;
H2.push(pi(-p[i].first, p1.second));
}
}
} else {
H2.push(pi(c[t - n] - p[i].first, t - n));
}
}
printf("%lld\n", ans);
return 0;
}