Menu
翘楚小站
  • 主页
  • 小项目
  • 算法
  • 摄影
翘楚小站

[NOIP2018]赛道修建(track)

Posted on 2019年11月3日2019年11月4日 by WonderBoy

Solution

以下引用大佬的题解:

看到题意描述第一反应就是先二分那个修建的 m 条赛道中长度最小的赛道的长度 k,然后 O(n) 或 O(n\log n) 判断。

那么怎么判断呢?

对于每个结点,把所有传上来的值 val 放进一个 multiset,其实这些值对答案有贡献就两种情况:

  • $ val \geq k$
  • $val_a+val_b \geq k$

那么第一种情况可以不用放进 multiset,直接答案 +1 就好了。
第二种情况就可以对于每一个最小的元素,在 multiset 中找到第一个 \geq k 的数,将两个数同时删去,最后把剩下最大的值传到那个结点的父亲。

Notice

当 a_i = 1 时,这是一张菊花图,程序可能会卡掉。
不过我们可以优化一下二分上界,先跑一遍 dfs,求出树的直径。

关于 set 的 erase 操作:
set.erase(iterator) 可以删除迭代器所指向元素,不过有可能会使得后继的迭代器失效,所以要优先删除后面的元素。

Model

二分模板

while (low <= high) {
    int mid = (low + high) >> 1;
    if (check(mid)) //可行
        low = mid + 1;
    else
        high = mid - 1;
    }

求最小值打印 high,求最大值打印 low。

求树的直径模板

int dfs1(int x, int fa) {
    int sum1 = 0, sum2 = 0; //保存上传的最大值和次大值
    for(int i = head[x]; i; i = edge[i].next) {
        int y = edge[i].to, z = edge[i].w;
        if(y == fa)
            continue;
        sum2 = max(sum2, dfs1(y,x) + z);
        if(sum1 < sum2)
            swap(sum1,sum2);
    }
    d = max(d, sum1 + sum2);
    return sum1;
}

上面程序中的 d 即为树的直径。

Code

// C-赛道修建(track)
// http://www.mfstem.org/contest/28/problem/C
// author: xzqiaochu
// status: AC
// time: xzqiaochu
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
const int NSZ = 5e4 + 7, MSZ = NSZ * 2;

int n, m;

int head[NSZ];
struct Edge {
    int to, w, next;
} edge[MSZ];

int up, k, cnt;
multiset<int> s[NSZ];

inline void addEdge(int x, int y, int z) {
    static int tot = 0;
    edge[++tot].to = y, edge[tot].w = z;
    edge[tot].next = head[x], head[x] = tot;
}

//求树的直径
int dfs1(int x, int fa) {
    int sum1 = 0, sum2 = 0;
    for(int i = head[x]; i; i = edge[i].next) {
        int y = edge[i].to, z = edge[i].w;
        if(y == fa)
            continue;
        sum2 = max(sum2, dfs1(y,x) + z);
        if(sum1 < sum2)
            swap(sum1,sum2);
    }
    up = max(up, sum1 + sum2);
    return sum1;
}

int dfs(int x, int fa) {
    s[x].clear();
    for (int i = head[x]; i; i = edge[i].next) {
        int y = edge[i].to, z = edge[i].w;
        if (y == fa)
            continue;
        int val = dfs(y, x) + z;
        if (val >= k)
            cnt++;
        else
            s[x].insert(val);
    }
    int maxn = 0;
    while (!s[x].empty()) {
        if (s[x].size() == 1)
            return max(maxn, *s[x].begin());
        multiset<int>::iterator it;
        it = s[x].lower_bound(k - *s[x].begin());
        if (it == s[x].begin() && s[x].count(*it) == 1)
            it++;
        if (it == s[x].end()) {
            maxn = max(maxn, *s[x].begin());
            s[x].erase(s[x].begin());
        } else {
            cnt++;
            s[x].erase(it); //先删除后面的元素
            s[x].erase(s[x].begin());
        }
    }
    return maxn;
}

bool check(int x) {
    k = x, cnt = 0;
    dfs(1, 0);
    if (cnt >= m)
        return true;
    else
        return false;
}

int main() {
    // freopen("track.in", "r", stdin);
    // freopen("track.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n - 1; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        addEdge(x, y, z), addEdge(y, x, z);
    }
    dfs1(1, 0); //初始化二分上界
    int low = 1, high = up;
    while (low <= high) {
        int mid = (low + high) >> 1;
        if (check(mid)) //可行
            low = mid + 1;
        else
            high = mid - 1;
    }
    int ans = high;
    printf("%d", ans);
    return 0;
}
  • NOIP
  • 二分
  • 信息学
  • 树
  • 发表评论 取消回复

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

    标签

    Arduino CSP DIY NOIP python tensorflow 一中文创 二分 人工智能 信息学 动态规划 图论 徐州一中 摄影 撷秀极客社区 数学 数论 最短路 树 模拟 洛谷 电子 短片 航拍 递归

    分类目录

    文章归档

    近期评论

    • 王清筠发表在《【徐州一中】再一次出发》
    • 王清筠发表在《测绘伏安特性曲线(I-U图像)》
    • xzqiaochu发表在《测绘伏安特性曲线(I-U图像)》
    • xzqiaochu发表在《测绘伏安特性曲线(I-U图像)》
    • 晨鹤发表在《测绘伏安特性曲线(I-U图像)》

    友情链接

    清筠小站
    晨鹤小站(。・∀・)ノ゙

    ©2021 翘楚小站 | 苏ICP备18005311号 | Powered by WordPress & Superb Themes