NOIp2012 瘟情控制

先二分一下所需时间,然后考虑一下怎么 check?

显然一支军队在满足时间限制的前提下,深度一定是小越优。用倍增优化跳的过程。但是可能会有子树没被控制,所以要用那些能够跳到根的结点去控制那些子树。对于一个可跳到根的结点,要么留在跳上来的那棵子树,要么通往根的另一端去控制别的子树。去控制别的子树,得先保证自己跳上来的那棵子树被控制了,要么是有多个结点,要么是别的结点来控制。让别的结点来控制自己的结点,自己出去帮别的结点是最优的结果当且仅当自己的子树到根的边长比来帮忙的结点与自己去帮的结点的边还要短。所以将那些需要被控制的子树与能到根的结点分别按父边长与剩余时间升序排序,每个结点找自己能控制的父边长最短的结点,如果扫到一个结点自己的子树还没被控制,说明不会更优,自己就接管自己的子树。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

typedef long long LL;

const int MAXN = 5e5;

int n, m, tot1, tot2, edge;
int pos[MAXN | 1], firstE[MAXN | 1], father[20][MAXN | 1], size[MAXN | 1];
LL fwther[20][MAXN | 1];
bool f[MAXN | 1], vis[MAXN | 1];

struct Edge {
  int to, w, nxt;
  Edge() {}
  Edge(int a, int b, int c) : to(b), w(c), nxt(firstE[a]) {}
} e[MAXN << 1];

struct Node {
  int w, id;
  Node() {}
  Node(int a, int b) : w(a), id(b) {}
  friend bool operator < (const Node &lhs, const Node &rhs) {
    return lhs.w < rhs.w;
  }
} a[MAXN | 1], b[MAXN | 1];

inline int read() {
  register int x = 0;
  register char ch = getchar();
  while(!isdigit(ch)) ch = getchar();
  while(isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}

inline void addEdge(int a, int b, int c) {
  e[++edge] = Edge(a, b, c);
  firstE[a] = edge;
}

void dfs(int x) {
  for(int i = 1; i < 20; ++i) {
    father[i][x] = father[i - 1][father[i - 1][x]];
    fwther[i][x] = fwther[i - 1][x] + fwther[i - 1][father[i - 1][x]];
  }
  size[x] = 1;
  for(int k = firstE[x]; k; k = e[k].nxt) {
    int to = e[k].to, w = e[k].w;
    if(to == father[0][x]) continue;
    father[0][to] = x;
    fwther[0][to] = w;
    dfs(to);
    size[x] += size[to];
  }
}

void dfs2(int x) {
  if(size[x] == 1 && x != 1) return;
  int t = 1;
  for(int k = firstE[x]; k; k = e[k].nxt) {
    int to = e[k].to;
    if(to == father[0][x]) continue;
    dfs2(to);
    t &= f[to];
  }
  if(t) f[x] = 1;
}

bool check(LL x) {
  tot1 = tot2 = 0;
  memset(f, 0, sizeof(f));
  memset(vis, 0, sizeof(vis));
  for(int i = 1; i <= m; ++i) {
    int jp = pos[i];
    LL wsum = 0;
    for(int j = 19; ~j; --j) {
      if(father[j][jp] && father[j][jp] != 1 && wsum + fwther[j][jp] <= x) {
        wsum += fwther[j][jp];
        jp = father[j][jp];
      }
    }
    if(father[0][jp] == 1 && wsum + fwther[0][jp] < x) a[++tot1] = Node(x - wsum - fwther[0][jp], jp);
    else f[jp] = 1;
  }
  dfs2(1);
  for(int k = firstE[1]; k; k = e[k].nxt) if(f[e[k].to] == 0) b[++tot2] = Node(e[k].w, e[k].to);
  std::sort(a + 1, a + tot1 + 1);
  std::sort(b + 1, b + tot2 + 1);
  int p = 1, cnt = 0;
  for(int i = 1; i <= tot1; ++i) {
    if(!f[a[i].id]) {
      f[a[i].id] = 1;
      ++cnt;
    } else {
      while(p <= tot2 && f[b[p].id]) ++p;
      if(p > tot2) break;
      if(b[p].w <= a[i].w) {
        f[b[p].id] = 1;
        ++cnt;
      }
    }
  }
  return cnt >= tot2;
}

int main() {
  n = read();
  LL l = 0, r = 0, ans = 1e18;
  for(int i = 1; i < n; ++i) {
    int u = read(), v = read(), w = read();
    addEdge(u, v, w);
    addEdge(v, u, w);
    r += w;
  }
  m = read();
  for(int i = 1; i <= m; ++i) pos[i] = read();
  dfs(1);
  while(l <= r) {
    LL mid = (l + r) >> 1;
    if(check(mid)) {
      ans = mid;
      r = mid - 1;
    } else l = mid + 1;
  }
  printf("%lld\n", ans == 1e18 ? -1 : ans);
  return 0;
}
最后修改:2019 年 08 月 16 日 11 : 10 AM

发表评论