357. 疫情控制

发表于 分类于 阅读次数： Waline： 本文字数： 1.4k 阅读时长 ≈ 5 分钟

考点

  • 贪心
  • 二分
  • LCA

题解

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
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e4 + 50, lg = (int)(log2(maxn)) + 1;
int tot, head[maxn], ver[maxn << 1], nxt[maxn << 1], edge[maxn << 1];
int n, m, d[maxn], f[maxn][lg], army[maxn];
ll dist[maxn];
queue<int> q;
// 该结点为根的子树是否堵住
bool block[maxn];
int cnt;
// 二类军队
pair<ll, int> a[maxn];
int num;
// 根结点的孩子中，有哪些不能堵住的
int son[maxn];
// 二类军队有没有被用过
bool used[maxn];

void add(int x, int y, int z) {
  ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}

void bfs() {
  d[1] = 1;
  q.push(1);
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = head[x]; i; i = nxt[i]) {
      int y = ver[i];
      if (d[y]) continue;
      q.push(y);
      d[y] = d[x] + 1;
      dist[y] = dist[x] + edge[i];
      f[y][0] = x;
      for (int k = 1; k < lg; ++k) f[y][k] = f[f[y][k - 1]][k - 1];
    }
  }
}

// 向上爬，直到根结点的孩子为止
// pair<ll, int>：剩余时间，到达结点
pair<ll, int> go(int x, ll mid) {
  for (int i = lg - 1; i >= 0; --i) {
    if (f[x][i] > 1 && dist[x] - dist[f[x][i]] <= mid) {
      mid -= dist[x] - dist[f[x][i]];
      x = f[x][i];
    }
  }
  return make_pair(mid, x);
}

// 不考虑二类军队，只考虑一类军队
// 此刻根结点到各个叶子节点的连通性
void dfs(int x, int f) {
  bool all_child_covered = 1;
  bool is_leaf = 1;
  for (int i = head[x]; i; i = nxt[i]) {
    int y = ver[i];
    if (y == f) continue;
    dfs(y, x);
    is_leaf = 0;
    all_child_covered &= block[y];
    if (x == 1 && !block[y]) son[++num] = y;
  }
  block[x] = block[x] || (all_child_covered && !is_leaf);
}

bool cmp(int x, int y) { return dist[x] < dist[y]; }

bool check(ll mid) {
  memset(block, 0, sizeof(block));
  memset(used, 0, sizeof(used));
  num = cnt = 0;
  for (int i = 1; i <= m; ++i) {
    pair<ll, int> t = go(army[i], mid);
    ll rst = t.first;
    int x = t.second;
    if (f[x][0] > 1)
      // 一类军队只能停在原地堵人
      block[x] = 1;
    else
      // 每个二类军队还可能出去帮人，按减去根后的距离排序
      a[++cnt] = {rst - dist[x], x};
  }
  dfs(1, 0);
  sort(a + 1, a + 1 + cnt);
  for (int i = 1; i <= cnt; ++i) {
    ll rst = a[i].first;
    int x = a[i].second;
    // 剩余路程小于到根距离，并且当前子树没被堵住
    // 那就把当前节点留下，否则全部拿去帮其他人
    if (rst < dist[x] && !block[x]) {
      block[x] = used[i] = 1;
    }
  }
  sort(son + 1, son + 1 + num, cmp);
  // 同向双指针
  for (int i = 1, j = 1; i <= num; ++i) {
    // 已经用某个二类军队堵住了
    if (block[son[i]]) continue;
    while (j <= cnt && (used[j] || a[j].first < dist[son[i]])) ++j;
    if (j > cnt) return false;
    ++j;
  }
  return true;
}

int main() {
  scanf("%d", &n);
  int x, y, z;
  ll sum = 0;
  for (int i = 1; i < n; ++i) {
    scanf("%d%d%d", &x, &y, &z);
    add(x, y, z), add(y, x, z);
    sum += z;
  }
  scanf("%d", &m);
  for (int i = 1; i <= m; ++i) scanf("%d", &army[i]);
  bfs();
  // 二分答案，最后取左边界
  ll l = 0, r = sum;
  while (l <= r) {
    ll mid = (l + r) >> 1;
    if (check(mid))
      r = mid - 1;
    else
      l = mid + 1;
  }
  printf("%lld\n", l > sum ? -1 : l);
  return 0;
}

思路

第一部分

根据题意，要尽可能地阻挡根节点到叶子节点的连通性，显然希望所有的军队往上冲。

因为树是一层一层发散的，越往上，能控制的叶子节点就越多。

故而很容易想到答案二分，在满足条件的情况下，选择向上冲刺距离最短的即为所求。

第二部分

最终的冲刺结果一定分成两份：

  1. 第一类军队，到不了根节点

    这类军队只能停留在原地堵人。

  2. 第二类军队，能到达根节点

    把这类军队先留在根节点的孩子节点上待命，用{rst , x}来保存至a数组，

    其中rst代表军队x可以跨过根节点多长距离。

    因为这类军队可以选择留在原地堵人，也可以选择跨过根节点，去帮根节点的其他孩子堵人。

    为什么不去根节点的孩子的孩子堵人？因为这是很明显的贪心策略。

    由于路径是非负数，越往下开销越大，能堵的子树范围也更小，肯定不会优于直接去赌根节点的孩子。

根据上面描述，作图如下：

第三部分

先只考虑一类军队对连通性的影响，因为它们只能堵在原地，全局dfs一遍即可。

当然，只需要记录根节点孩子的连通性，如果该孩子依旧可以访问到任何一个叶子节点，那么记录到son数组。

现在的问题是，如何决定二类军队到底是留在原地，还是去帮其他人呢？

假设情况如下，有个点还需要人去填充，A点有1个军队，B点有2个军队。

很容易发现一个规律，如果q < p并且该军队离开后反而打通了连通性，那么该军队就待在原地。

除此外的其他情况都可以去帮别人。

道理很简单。

A点出发去堵人，需要消耗p + q，那么B点需要r + p来帮你堵上。

可问题在于，如果是B点去堵人，需要消耗r + q < r + p，

也就是说，该情况下让B点去堵人反而比A点堵人更优。

这也是一个贪心策略，同样可以堵人，显然留下更长的距离更好，这样能满足更多的条件。

根据上面的策略，从a筛选一批二类军队留下。

第四部分

son是需要军队的根节点孩子数组，a是空闲军队的根节点孩子数组，

son对根节点距离进行排序，a对可用距离rst排序，

同时对两个数组进行单向双指针即可。