[WC2010]重建计划 题解

[WC2010]重建计划 题解

题目地址:洛谷:【P4292】[WC2010]重建计划 – 洛谷、BZOJ:Problem 1758. — [Wc2010]重建计划

题目描述

1758 - [WC2010]重建计划 题解

题意简述

给你一棵树,求长度在[L, U]范围内的树链的边权平均值的最大值。

输入输出格式

输入格式:
第一行包含一个正整数N,表示X国的城市个数。
第二行包含两个正整数L、U,表示政府要求的第一期重建方案中修建道路数的上下限。
接下来的N-1行描述重建小组的原有方案,每行三个正整数ai, bi, vi,分别表示道路(ai, bi),其价值为vi。其中城市由1…N标号。

输出格式:
仅包含一行,为一个实数AvgValue,即最大平均价值。
小数点后保留三位。

输入输出样例

输入样例#1:

4 
2 3 
1 2 1 
1 3 2 
1 4 3

输出样例#1:

2.500

说明

新方案中选择路径(3, 1), (1, 4)可以得到的平均价值为2.5,为最大平均价值。
对于20%的数据,N ≤ 5 000;
另有30%的数据,N ≤ 100 000, 原有方案恰好为一条路径(链);
对于100%的数据,N ≤ 100 000, 1 ≤ L ≤ U ≤ N-1, vi ≤ 10^6。

题解

整个树找树链可以考虑使用点分治。
对于每个重心,我们考虑二分答案,验证的时候找两条子树到重心的路径拼起来长度在范围内的,或者一条路径长度就在范围内的,在处理边权和的时候在每个边权上减掉答案,则只需要判断边权和是否不小于0即可。
由于对于以前找到过的每一个深度的链,只需要存下边权和最大值,就可以直接拿来判断了。而枚举每个深度去遍历合法区间,会造成复杂度退化为$O(n^2)$。我们考虑单调队列优化这一过程,从浅到深枚举当前遍历子树的每个节点,对应的在以前找到过的深度区间可以确定为[L-d, R-d],由于遍历的顺序单调,单调队列可以倒着从深到浅维护最大值来判定,遍历节点时使用BFS,这样节点的遍历顺序就是从浅到深单调的了,这样判定的复杂度是$O(n)$的了。
单调队列的复杂度其实应该是$O(之前找到过的最大深度)$的,因此,我们可以对每一棵子树的深度进行排序,从浅的子树开始遍历,可以优化时间,不过我采用了快排,排序复杂度会多一个$\log n$。
另外,本题有一定的卡常数成分,有以下几个卡常的地方可以作为参考:

  1. 每次遍历需要初始化最大值数组,可以到用的时候再初始化(参见121~123行);
  2. 对于大小小于L的子树,是找不到符合条件的链的,因此可以不用递归下去处理(参见145行);
  3. 可以使用计数排序代替快排(没写);
  4. 读入优化,fread(我的文件头);
  5. 存树用邻接表而不是vector;
  6. 自己实现的max函数代替STL的;
  7. 手写BFS的队列;
  8. 二分答案的时候,可以将左端点设为已经找到的解,右端点设为最大边权,这样每次二分只会去找比当前解更优的解更新。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

inline int max(int a, int b) {
    return a > b ? a : b;
}

inline double max(double a, double b) {
    return a > b ? a : b;
}

const int MAXN = 100005;
const double EPS = 1e-4;

int n, L, U;
double ans;

struct Edge {
    int to, w, nxt;
} gra[MAXN << 1];
int head[MAXN], tot;

inline void addedge(int u, int v, int w) {
    gra[tot] = Edge {v, w, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, w, head[v]}; head[v] = tot++;
}

bool vis[MAXN];
int siz[MAXN], rt, rtsiz;

inline void findrt(int u, int fa, int tot) {
    siz[u] = 1; int msiz = 0;
    for(register int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(vis[v] || v == fa) continue;
        findrt(v, u, tot);
        siz[u] += siz[v];
        msiz = max(msiz, siz[v]);
    }
    msiz = max(msiz, tot - siz[u]);
    if(msiz < rtsiz) {
        rt = u; rtsiz = msiz;
    }
}

int fa[MAXN], dep[MAXN], que[MAXN], deq[MAXN];
double dis[MAXN];

int tdep[MAXN], subt[MAXN], subw[MAXN], stot;

inline bool cmp(int a, int b) {
    return tdep[a] < tdep[b];
}

inline int dfs(int u, int fa, int dep) {
    int mxdep = dep;
    for(register int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(vis[v] || v == fa) continue;
        mxdep = max(mxdep, dfs(v, u, dep + 1));
    }
    return mxdep;
}

double mx[MAXN];

inline bool check(int u, double mid) {
    int mxdep = 0;
    stot = 0;
    for(register int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        subt[++stot] = v;
        subw[v] = gra[i].w;
        tdep[v] = dfs(v, u, 1);
    }
    std::sort(subt + 1, subt + stot + 1, cmp);
    for(register int i = 1; i <= stot; i++) {
        int v = subt[i];
        if(vis[v]) continue;
        int hd = 0, tl = 1; fa[v] = u; dep[v] = 1; dis[v] = subw[v] - mid; que[0] = v;
        while(hd < tl) {
            int uu = que[hd++];
            for(register int j = head[uu]; ~j; j = gra[j].nxt) {
                int vv = gra[j].to;
                if(vis[vv] || vv == fa[uu]) continue;
                fa[vv] = uu;
                dep[vv] = dep[uu] + 1;
                dis[vv] = dis[uu] + gra[j].w - mid;
                que[tl++] = vv;
            }
        }
        int l = 1, r = 0, now = mxdep;
        for(register int j = 0; j < tl; j++) {
            int p = que[j];
            while(dep[p] + now >= L && now >= 0) {
                while(l <= r && mx[deq[r]] < mx[now]) r--;
                deq[++r] = now; now--;
            }
            while(l <= r && dep[p] + deq[l] > U) l++;
            if(l <= r && dis[p] + mx[deq[l]] + EPS >= 0) return true;
        }
        for(register int j = mxdep + 1; j <= dep[que[tl - 1]]; j++) {
            mx[j] = -1e9;
        }
        for(register int j = 0; j < tl; j++) {
            int p = que[j];
            mx[dep[p]] = max(mx[dep[p]], dis[p]);
        }
        mxdep = max(mxdep, dep[que[tl - 1]]);
    }
    return false;
}

int lim;

inline void divide(int u) {
    register double l = ans, r = lim, mid;
    while(r - l > EPS) {
        mid = (l + r) / 2;
        if(check(u, mid)) l = mid; else r = mid;
    }
    ans = l;
    vis[u] = true;
    for(register int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(vis[v] || siz[v] < L) continue;
        rt = 0; rtsiz = n; findrt(v, u, siz[v]);
        divide(rt);
    }
}

int main() {
    memset(head, -1, sizeof(head));
    n = readint(); L = readint(); U = readint();
    for(register int i = 1, a, b, c; i < n; i++) {
        a = readint(); b = readint(); c = readint();
        lim = max(lim, c);
        addedge(a, b, c);
    }
    rt = 0; rtsiz = n; findrt(1, 0, n);
    divide(rt);
    printf("%.3lf", ans);
    return 0;
}


发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据