首页 > [NOIP2007]树网的核
开通博客写题解
头像 savage
发表于 2019-09-07 16:07:42
算法知识点: 二分，树的直径，贪心，树的遍历 复杂度： 解题思路： 二分最小偏心距，判断在直径上是否存在一段长度不超过 的路径，使得其余所有点到路径的距离小于等于枚举的值。 接下来在直径上找到与 的距离不超过 的前提下，距离最远的节点，作为节点 。类似地，在直径上找到与 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 savage
发表于 2019-08-31 14:46:24
题目描述 设T=(V, E, W) 是一个无圈且连通的无向图（也称为无根树），每条边带有正整数的权，我们称T为树网（treenetwork），其中V, E分别表示结点与边的集合，W表示各边长度的集合，并设T有n个结点。 路径：树网中任何两结点 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 QAQ天战QAQ
发表于 2020-01-13 13:06:39
以下都是答案#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <vector>using namespace std;< 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 louhc
发表于 2019-08-23 14:49:47
思路 通过大胆猜想与小心伪证,我们可以得到一个结论: 在任何一条直径求得的最小偏心距都是相等的. 有了这个结论,我们就可以乱搞啦.对于直径,若选取的核为,最小偏心距只有可能为,,或者是选取整条直径为核时的最小偏心距.(十分好证)那么先求出某条直径的最小偏心距,然后在直径两端分别为虎一个指针,不断 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”