bzoj 1758 重建计划

题意：

给定一棵有边权的树和两个数 \(L, R (L\leq R)\)，求一条简单路径，使得这条路径经过的边数在 \(L, R\) 之间且路径经过的边的边权的平均值最大

背景：

NewTrain里面的题

坑了很长时间

题解：

显然是分数规划

二分答案，然后变成判断是否有路径的边权和大于等于 \(0\)

考虑点分治，每一层保留下来每个深度对应的最大边权和，然后因为对于一个子树而言，随着深度增加，合法区间是向左移动的，可以用单调队列维护

复杂度？

对于当前的重心，处理某一棵子树的代价为 \(\max(dep, prev\_dep)\)，其中 \(dep\) 表示当前子树的最大深度，\(prev\_dep\) 表示之前处理的子树的最大深度

为了保证复杂度，我们将子树按照深度排序，可以使得 \(dep \geq prev\_dep\) 对于任何子树成立，那么处理一层的代价变为 \(\sum dep \leq size\)

我们发现，不管当前二分的答案是多少，重心的顺序相同，并且对于固定的重心而言，其子树的深度顺序相同，所以都可以预处理，或者直接在点分治内部二分，可以降低常数

（到底是在里面二分快还是在外面二分快啊？好像网上的代码都是在里面二分的，但是栋栋说在外面二分快。。。)

代码：

// Copyright lzt

#include<stdio.h>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<cmath>

#include<iostream>

#include<queue>

#include<string>

#include<ctime>

using namespace std;

typedef long long ll;

typedef std::pair<int, int> pii;

typedef long double ld;

typedef unsigned long long ull;

typedef std::pair<long long, long long> pll;

#define fi first

#define se second

#define pb push_back

#define mp make_pair

#define rep(i, j, k)  for (register int i = (int)(j); i <= (int)(k); i++)

#define rrep(i, j, k) for (register int i = (int)(j); i >= (int)(k); i--)

#define Debug(...) fprintf(stderr, __VA_ARGS__)

inline ll read() {

  ll x = 0, f = 1;

  char ch = getchar();

  while (ch < '0' || ch > '9') {

    if (ch == '-') f = -1;

    ch = getchar();

  }

  while (ch <= '9' && ch >= '0') {

    x = 10 * x + ch - '0';

    ch = getchar();

  }

  return x * f;

}

const int maxn = 100100;

double MX;

int n, L, R, tot, root, rf, mxdep, nwdep;

int head[maxn], to[maxn << 1], nxt[maxn << 1], len[maxn << 1];

int sz[maxn];

bool vis[maxn];

double res, xx, f[maxn], g[maxn];

vector<pii> vec;

inline void addedge(int x, int y, int l) {

  to[++tot] = y; nxt[tot] = head[x]; head[x] = tot; len[tot] = l;

  to[++tot] = x; nxt[tot] = head[y]; head[y] = tot; len[tot] = l;

}

inline void dfs1(int u, int pa) {

  sz[u] = 1;

  for (int i = head[u]; i; i = nxt[i]) {

    int v = to[i];

    if (v == pa || vis[v]) continue;

    dfs1(v, u); sz[u] += sz[v];

  }

}

inline int getroot(int u, int pa, int S) {

  for (int i = head[u]; i; i = nxt[i]) {

    int v = to[i];

    if (v == pa || vis[v]) continue;

    if (sz[v] * 2 > S) return getroot(v, u, S);

  }

  rf = pa;

  return u;

}

inline bool cmp (pii x, pii y) {

  return sz[x.fi] < sz[y.fi];

}

inline void dfs2(int u, int pa, double l, int d) {

  if (d > R) return;

  g[d] = max(g[d], l); nwdep = max(nwdep, d);

  for (int i = head[u]; i; i = nxt[i]) {

    int v = to[i];

    if (vis[v] || v == pa) continue;

    dfs2(v, u, l + len[i] - xx, d + 1);

  }

}

int q[maxn];

int h, t;

inline bool ok(int u) {

  bool flag = 0;

  mxdep = 0;

  rep(i, 0, vec.size() - 1) {

    nwdep = 0;

    dfs2(vec[i].fi, u, vec[i].se - xx, 1);

    h = 1, t = 0;

    rrep(j, min(R, mxdep), L) {

      if (j > mxdep) continue;

      double nw = f[j];

      while (t >= h && nw >= f[q[t]]) t--;

      q[++t] = j;

    }

    if (t >= h && f[q[h]] >= 0) {

      flag = 1;

    } else {

      rep(j, 1, nwdep) {

        double nw = f[L - j];

        while (nw >= f[q[t]] && t >= h) t--;

        q[++t] = L - j;

        while (q[h] + j > R) h++;

        if (q[h] <= mxdep && q[h] + j >= L && g[j] + f[q[h]] >= 0) {

          flag = 1;

          break;

        }

      }

    }

    mxdep = max(mxdep, nwdep);

    rep(j, 1, nwdep) f[j] = max(f[j], g[j]), g[j] = -1e9;

    if (flag) break;

  }

  rep(j, 1, mxdep) f[j] = -1e9;

  return flag;

}

void solve(int u, int pa) {

  dfs1(u, pa);

  root = getroot(u, pa, sz[u]);

  sz[rf] = sz[u] - sz[root];

  vec.clear();

  for (int i = head[root]; i; i = nxt[i]) {

    int v = to[i];

    if (vis[v]) continue;

    vec.pb(mp(v, len[i]));

  }

  sort(vec.begin(), vec.end(), cmp);

  double le = res, ri = MX;

  while (ri - le > 1e-4) {

    xx = (le + ri) * 0.5;

    if (ok(root)) le = xx;

    else ri = xx;

  }

  res = le;

  vis[root] = 1;

  for (int i = head[root]; i; i = nxt[i]) {

    if (vis[to[i]] || sz[to[i]] <= L) continue;

    solve(to[i], root);

  }

}

void work() {

  n = read(); L = read(), R = read();

  rep(i, 1, n - 1) {

    int x = read(), y = read(), l = read();

    addedge(x, y, l); MX = max(MX, l * 1.0);

  }

  rep(i, 1, n) f[i] = g[i] = -1e9;

  solve(1, 0);

  printf("%.3lf\n", res);

}

int main() {

  #ifdef LZT

    freopen("in", "r", stdin);

  #endif

  work();

  #ifdef LZT

    Debug("My Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);

  #endif

}

Review

思维难度低，代码难度高

（或者说是我不太会写代码。。。）

巴特西

[bzoj 1758] 重建计划

bzoj 1758 重建计划

题意：

背景：

题解：

代码：

Review

最新文章

热门文章