P8021 [ONTAK2015] Bajtman i Okrągły Robin 题解

发表于 更新于 分类于 本文字数： 846 阅读时长 ≈ 2 分钟

true
Bajtman i Okrągły Robin
ONTAK 2015
省选/NOI-
#9d3dcf
  • Luogu P8021
  • BZOJ #4276

我们考虑这样想：

假如商店每个长度为 1 的时间段内只能够被抢劫一次，那么你就只需要站在商店门口盯着就可以了，而把问题抛给了强盗们去解决了——而强盗们的问题是，如何规划抢劫时间才能使被抢劫的财物价值总和最大。

对于这样的问题，我们可以想到带权二分图最大匹配，然后就转化成为了最大费用最大流问题。

我们将每一个强盗和每一个长度为 1 的时间段都设为一个点，然后让每一个强盗向其可以抢劫的时间段区间内的每一个时间段连一条容量为 1、费用为 $c_i$ 的边。
然后每一个强盗向源点连边，每一个时间段向汇点连边，这两次连边都是容量为 1、费用为 0。

然后我们会发现，这样连边的话边的数量是 $O(n^2)$ 级别的，无法达到我们的要求。

于是我们就引入了线段树优化建图这样一种节约边数的方式，使得边的数量减小为 $O(\log{n})$ 级别的。

线段树优化建图的大意就是将线段树的区间作为一个中转点，由其向其子节点连边，而不是直接连边。

我们建立线段树的时候，与正常情况下建立线段树的方式是一样的，只不过这里不需要维护任何信息，只需要将每一个叶子节点连向汇点，同时将一个节点与其左右子节点（如果有的话）连边即可。

这道题里因为每一个时间段只能够被抢劫一次（上面说了），所以代表其的点向汇点连的边容量为 1、费用为 0。

但是线段树中父亲节点向子节点连的边的容量就不能是 1 了，必须是 $+\infty$ 才能保证其覆盖的区间都可以被抢劫。

这里写的时候不是特别放心，在结构体里面存了一个节点编号，其实在线段树节点有序的情况下不需要存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void build(int p, int l, int r)
{
    tr[p].l = l, tr[p].r = r;
    tr[p].id = ++cnt;
    if(l == r)
    {
        add(tr[p].id, T, 1, 0);
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    add(tr[p].id, tr[p << 1].id, INF, 0);
    add(tr[p].id, tr[p << 1 | 1].id, INF, 0);
    return;
}

然后就是区间连边。

我们其实只需要向线段树区间加那样，向每一个最长的完全被覆盖的区间连一条容量为 1、费用为 $c_i$ 的边即可。

1
2
3
4
5
6
7
8
9
10
11
12
void seglnk(int p, int l, int r, int k)
{
    if(tr[p].l >= l && tr[p].r <= r)
    {
        add(k + 1, tr[p].id, 1, -c[k]);
        return;
    }
    int mid = (tr[p].l + tr[p].r) >> 1;
    if(l <= mid)seglnk(p << 1, l, r, k);
    if(r > mid)seglnk(p << 1 | 1, l, r, k);
    return;
}

最后注意一个小细节：线段树内的叶子结点代表的区间是 $[a,a]$，而这里要求的最小区间是 $[a,a+1]$，所以我们可以将右端点自减一来替代一下。

最后放总的代码：

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2000010, M = 2000010, INF = 1e8;
int n, m, S, T;
int a[N], b[N], c[N];
int h[N], e[M], f[M], w[M], ne[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];

void add(int a, int b, int c, int d)
{
    e[idx] = b, f[idx] = c, w[idx] = d, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, f[idx] = 0, w[idx] = -d, ne[idx] = h[b], h[b] = idx++;
}

struct SegTree
{
    int l, r;
    int id;
}tr[N << 3];
int cnt;

void build(int p, int l, int r)
{
    tr[p].l = l, tr[p].r = r;
    tr[p].id = ++cnt;
    if(l == r)
    {
        add(tr[p].id, T, 1, 0);
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    add(tr[p].id, tr[p << 1].id, INF, 0);
    add(tr[p].id, tr[p << 1 | 1].id, INF, 0);
    return;
}
void seglnk(int p, int l, int r, int k)
{
    if(tr[p].l >= l && tr[p].r <= r)
    {
        add(k + 1, tr[p].id, 1, -c[k]);
        return;
    }
    int mid = (tr[p].l + tr[p].r) >> 1;
    if(l <= mid)seglnk(p << 1, l, r, k);
    if(r > mid)seglnk(p << 1 | 1, l, r, k);
    return;
}

bool spfa()
{
    int hh = 0, tt = 1;
    memset(d, 0x3f, sizeof(d));
    memset(incf, 0, sizeof(incf));
    q[0] = S, d[S] = 0, incf[S] = INF;
    while(hh != tt)
    {
        int t = q[hh++];
        if(hh == N) hh = 0;
        st[t] = false;

        for(int i = h[t]; ~i; i = ne[i])
        {
            int ver = e[i];
            if(f[i] && d[ver] > d[t] + w[i])
            {
                d[ver] = d[t] + w[i];
                pre[ver] = i;
                incf[ver] = min(f[i], incf[t]);
                if(!st[ver])
                {
                    q[tt++] = ver;
                    if(tt == N) tt = 0;
                    st[ver] = true;
                }
            }
        }
    }

    return incf[T] > 0;
}

void EK(int &flow, int &cost)
{
    flow = cost = 0;
    while(spfa())
    {
        int t = incf[T];
        flow += t, cost += t * d[T];
        for(int i = T; i != S; i = e[pre[i] ^ 1])
        {
            f[pre[i]] -= t;
            f[pre[i] ^ 1] += t;
        }
    }
}
int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d", &n);
    S = 0, T = 1;
    int maxn = 0;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d%d", &a[i], &b[i], &c[i]);
        add(S, i + 1, 1, 0);
        maxn = max(maxn, b[i]);
    }
    cnt = n + 1;
    build(1, 1, maxn + 1);
    for(int i = 1; i <= n; i++)
        seglnk(1, a[i], b[i] - 1, i);
    int flow, cost;
    EK(flow, cost);
    printf("%d\n", -cost);
    return 0;
}