Tag-BFS

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2019-07-04 14:41:30 |  0 Comments  |  线段树 DP BFS

BZOJ 1999 树网的核[数据加强版] 树的直径+线段树

题解

此题原本是NOIP提高组一道压轴,这一改数据感觉可以放省选赛或者CCPC难题里面什么的了

鬼知道为什么我当初做这道题会YY出线段树做法,现在想想我自己都佩服我自己。

嘛写这篇算是权当复习一下思路了。

题目告诉我们最小偏心距是什么了……我们要求的就是选定一个长度不超过s的核(在直径上,也可以是点也可以是边)使得离这个核最远的点离这个核 的距离最小。

首先求直径是很好求的,两遍BFS就搞定了。

但是直径可能会有很多条,那我们就对每一条都要计算。

对于每一条直径,我们的答案一定是由两类值的最大值来组成:

1.非此直径上的点到当前选定的核的距离的最大值。

2.直径的两个端点到当前选定的核的距离的最大值。

我们考虑用两个指针(two-pointers)的思想,不断的在直径上移动我们选定的核的两端(保证长度不超过s),这样可以保证线性查询,而不是暴力枚举带来的平方复杂度的查询。

距离直径的两个端点的值很好求,只需要在移动指针的时候不断地修改就可以了。

至于非此直径上的点,我们可以预处理他们到每一个此直径上的点的距离的最大值,然后再不断移动核的两端的时候,我们发现,这其实就是求当前核所涵盖的区间上的点的最远距离的最大值,这个区间问题我们可以用线段树(或者树状数组)进行查询,这样就可以logn的复杂度内查询了。

对于每一条直径我们都这么操作来算出一个答案,最终取所有答案的最小值就是最小偏心距了。

代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int INF = 2147483647;
int get_num() {
    int num = 0;
    char c;
    bool flag = false;
    while ((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if (c == '-')
        flag = true;
    else num = c - '0';
    while (isd
Title - Artist
0:00