【题目来源】
洛谷：[P1099 NOIP 2007 提高组] 树网的核 - 洛谷
【题目描述】
设 \(T\)\(=\)\((V,E,W)\) 是一个无圈且连通的无向图（也称为无根树），每条边都有正整数的权，我们称 \(T\) 为树网（treenetwork），其中 \(V\)，\(E\) 分别表示结点与边的集合，\(W\) 表示各边长度的集合，并设 \(T\) 有 \(n\) 个结点。
路径：树网中任何两结点 \(a\)，\(b\) 都存在唯一的一条简单路径，用 \(d(a,b)\) 表示以 \(a,b\) 为端点的路径的长度，它是该路径上各边长度之和。我们称 \(d(a,b)\) 为 \(a,b\) 两结点间的距离。
\(D(v,P)=min\{d(v,u)\}\), \(u\) 为路径 \(P\) 上的结点。
树网的直径：树网中最长的路径称为树网的直径。对于给定的树网 T，直径不一定是唯一的，但可以证明：各直径的中点（不一定恰好是某个结点，可能在某条边的内部）是唯一的，我们称该点为树网的中心。
偏心距 \(ECC(F)\)：树网 \(T\) 中距路径 \(F\) 最远的结点到路径 \(F\) 的距离，即
\(ECC(F)=max\{D(v,F),v∈V\}\)
任务：对于给定的树网 \(T=(V,E,W)\) 和非负整数 \(s\)，求一个路径 \(F\)，他是某直径上的一段路径（该路径两端均为树网中的结点），其长度不超过 \(s\)（可以等于 \(s\)），使偏心距 \(ECC(F)\) 最小。我们称这个路径为树网 \(T=(V,E,W)\) 的核（Core）。必要时，\(F\) 可以退化为某个结点。一般来说，在上述定义下，核不一定只有一个，但最小偏心距是唯一的。
下面的图给出了树网的一个实例。图中，\(A−B\) 与 \(A−C\) 是两条直径，长度均为 \(20\)。点 \(W\) 是树网的中心，\(EF\) 边的长度为 \(5\)。如果指定 \(s=11\)，则树网的核为路径DEFG（也可以取为路径DEF），偏心距为 \(8\)。如果指定 \(s=0\)（或 \(s=1\)、\(s=2\)），则树网的核为结点 \(F\)，偏心距为 \(12\)。
【输入】
共 \(n\) 行。
第 \(1\) 行，两个正整数 \(n\) 和 \(s\)，中间用一个空格隔开。其中 \(n\) 为树网结点的个数，\(s\) 为树网的核的长度的上界。设结点编号以此为 \(1,2…,n\)。
从第 \(2\) 行到第 \(n\) 行，每行给出 \(3\) 个用空格隔开的正整数 \(u,v,w\)，依次表示每一条边的两个端点编号和长度。例如，2 4 7 表示连接结点 \(2\) 与 \(4\) 的边的长度为 \(7\)。
【输出】
一个非负整数，为指定意义下的最小偏心距。
【输入样例】
5 2
1 2 5
2 3 2
2 4 4
2 5 3
【输出样例】
5
【算法标签】
《洛谷 P1099 树网的核》 #模拟# #动态规划DP# #树形数据结构# #枚举# #最短路# #NOIP提高组# #2007#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 305; // 最大节点数int n; // 节点数量
int s; // 路径长度限制
int u, v, w; // 临时变量：起点、终点、权重
int vis[N]; // 访问标记数组
int st, ed; // 起点和终点
int dist[N]; // 距离数组
int maxx; // 最大距离
int router[N]; // 存储最长路径
int router_t[N]; // 临时存储路径
int len, len_t; // 路径长度
int ans; // 最终答案
int color[N]; // 标记是否在核心路径上vector<int> ve[N]; // 邻接表存储连接关系
vector<int> wi[N]; // 邻接表存储权重// 第一次DFS：找到树的直径的一个端点
void dfs_1(int x, int y)
{// 更新最长路径if (y > maxx){len = len_t;memcpy(router, router_t, sizeof(router)); // 复制路径maxx = y;}// 遍历所有邻接节点for (int i = 0; i < ve[x].size(); i++){int tmp_v = ve[x][i];if (vis[tmp_v])continue;// 更新距离和路径dist[tmp_v] = y + wi[x][i];vis[tmp_v] = 1;len_t++;router_t[len_t] = tmp_v;// 递归搜索dfs_1(tmp_v, y + wi[x][i]);// 回溯vis[tmp_v] = 0;len_t--;}
}// 第二次DFS：计算从核心路径出发的最远距离
void dfs_2(int x)
{// 更新最大距离ans = max(ans, dist[x]);// 遍历所有邻接节点for (int i = 0; i < ve[x].size(); i++){int tmp_v = ve[x][i];if (vis[tmp_v] || color[tmp_v])continue;// 更新距离并继续搜索vis[tmp_v] = 1;dist[tmp_v] = dist[x] + wi[x][i];dfs_2(tmp_v);// 回溯vis[tmp_v] = 0;}return;
}int main()
{// 输入节点数和路径长度限制cin >> n >> s;// 构建邻接表for (int i = 1; i < n; i++){cin >> u >> v >> w;ve[u].push_back(v);wi[u].push_back(w);ve[v].push_back(u);wi[v].push_back(w);}// 第一次DFS：找到直径的一个端点st = 1;vis[st] = 1;router_t[++len_t] = st;dfs_1(st, 0);// 第二次DFS：找到直径的另一个端点st = router[len];memset(vis, 0, sizeof(vis));memset(dist, 0, sizeof(dist));memset(router, 0, sizeof(router));memset(router_t, 0, sizeof(router_t));len = len_t = 0;len_t = 1;router_t[len_t] = st;maxx = 0;vis[st] = 1;dfs_1(st, 0);ed = router[len];// 寻找最优的核心路径ans = 1e9;for (int i = 1; i <= len; i++){for (int j = i; j <= len; j++){if (dist[router[j]] - dist[router[i]] > s)break;// 计算当前路径的最大偏心距int t = max(dist[router[i]], dist[router[len]] - dist[router[j]]);if (t < ans){ans = t;st = i;ed = j;}}}// 标记核心路径上的节点for (int i = st; i <= ed; i++)color[router[i]] = 1;// 从核心路径上的每个节点出发，计算最远距离for (int i = st; i <= ed; i++){memset(vis, 0, sizeof(vis));memset(dist, 0, sizeof(dist));vis[router[i]] = 1;dfs_2(router[i]);}// 输出最小偏心距cout << ans << endl;return 0;
}
【运行结果】
8 6
1 3 2
2 3 2
3 4 6
4 5 3
4 6 4
4 7 2
7 8 3
5