一站式网站建设有哪些,优秀的个人网站设计,织梦网站怎样上传到ftp,flash布局网站树的直径——树形 D P 、两次 B F S \Huge{树的直径——树形DP、两次BFS} 树的直径——树形DP、两次BFS 文章目录 树形DP两次BFS 不再详细解释代码#xff0c;只记录完整模板。 树形DP
可以计算负权边。
时间复杂度#xff1a; O ( n ) O(n) O(n)。
设 D [ x ] D[x] D[x]表… 树的直径——树形 D P 、两次 B F S \Huge{树的直径——树形DP、两次BFS} 树的直径——树形DP、两次BFS 文章目录 树形DP两次BFS 不再详细解释代码只记录完整模板。 树形DP
可以计算负权边。
时间复杂度 O ( n ) O(n) O(n)。
设 D [ x ] D[x] D[x]表示从节点 x x x出发走向以 x x x为根的字数能够到达的最远节点的距离设 y i y_i yi表示子节点 e d g e ( x , y ) edge(x,y) edge(x,y)表示边权则有 D [ x ] m a x 1 ≤ i ≤ t ( D [ y i ] e d g e ( x i , y i ) ) D[x]max_{1\le i\le t}(D[y_i]edge(x_i,y_i)) D[x]max1≤i≤t(D[yi]edge(xi,yi))
设F[x]为经过节点x的最长链长度则有 F [ x ] m a x 1 ≤ j i ≤ t ( D [ y i ] D [ y j ] e d g e ( x , y i ) e d g e ( x , y j ) ) F[x]max_{1\le ji\le t}(D[y_i]D[y_j]edge(x,y_i)edge(x,y_j)) F[x]max1≤ji≤t(D[yi]D[yj]edge(x,yi)edge(x,yj))
int res, n, b[N], d[N];
vectorPII a[N];
void dp(int x) {b[x] 1;for(int i 0; i a[x].size(); i ) {int t a[x][i].fi, u a[x][i].se;if(b[t]) continue;dp(t);res max(res, d[x] d[t] u);d[x] max(d[x], d[t] u);}
}void Solved() {cin n;for (int i 0; i n - 1; i) {int x, y, z; cin x y z;a[x - 1].push_back({y - 1, z});a[y - 1].push_back({x - 1, z});}dp(0); cout res endl;
}两次BFS
实现最长直径长度计算出直径上的具体节点。
无法计算负权边
时间复杂度 O ( n ) O(n) O(n)。
struct Node {int id, distance;};// 结点
struct Edge {int to, weight;}; // 边vectorvectorEdge tree; //用于存储树的结构
vectorbool visited; //标记
vectorint parent; //存放父节点Node bfs(int start) {// 第一次 BFS从任意结点开始找到最远的结点queueNode q;visited.assign(tree.size(), false);q.push({start, 0});visited[start] true;Node farthest {start, 0};while (!q.empty()) {Node current q.front(); q.pop();if (current.distance farthest.distance) farthest current;for (const Edge edge : tree[current.id]) {if (!visited[edge.to]) {visited[edge.to] true;q.push({edge.to, current.distance edge.weight});parent[edge.to] current.id; // 保存父节点信息}}}return farthest;
}vectorint diameter() {// 第二次 BFS从最远的结点开始找到直径的另一端Node start bfs(0);Node end bfs(start.id);vectorint path;path.push_back(end.id);// 从 end.id 向上回溯到 start.id得到直径上的所有节点int current end.id;while (current ! start.id) {current parent[current]; // 根据父节点数组回溯path.push_back(current);}reverse(path.begin(), path.end());path.push_back(end.distance); //将最长直径一并返回return path;
}int main() {int n; cin n;tree.resize(n); parent.resize(n, -1);for (int i 0; i n - 1; i) {int x, y, z; cin x y z;tree[x - 1].push_back({y - 1, z});tree[y - 1].push_back({x - 1, z});}vectorint path diameter();cout path.back() endl; //输出最长直径path.pop_back(); //将答案删除for (int node : path) //输出最长直径具体节点cout node 1 ;return 0;
}
