怎么做网站站内搜索,正规网站模板设计,许昌网站建设科技公司,wordpress 安装七牛树的直径与重心
或许更好的阅读体验
树的直径求解方法一
思路
先选取一个点rt作为根节点#xff0c;dfs去找到一个最长路径的点U#xff0c;然后通过这个点去dfs#xff0c;找到路径最长的点V#xff0c;U-V就是这课树的直径。
证明正确性#xff1a;
假如rt在直…树的直径与重心
或许更好的阅读体验
树的直径求解方法一
思路
先选取一个点rt作为根节点dfs去找到一个最长路径的点U然后通过这个点去dfs找到路径最长的点VU-V就是这课树的直径。
证明正确性
假如rt在直径上的话最长路径的点U一定是直径的一个端点这一点是显然的。
假如rt不在直径上那么从这个点出发也一定可以找到一条路到达直径上一点接下来就如同上面一样了无非就是在真正的dis上再加上一段固定的value对我们最后的直径端点查找并无影响。
代码
#include bits/stdc.husing namespace std;typedef long long ll;
const int N 1e5 10;int head[N], to[N], value[N], nex[N], cnt;
int n, ans, dis[N];inline ll read() {ll x 1, s 0; char c;c getchar();while(c 0 || c 9) {if(c -) x -1;c getchar();}while(c 0 c 9) {s (s 1) (s 3) (c ^ 48);c getchar();}return x * s;
}void add(int x, int y, int w) {to[cnt] y;nex[cnt] head[x];value[cnt] w;head[x] cnt;
}void dfs(int rt, int fa) {for(int i head[rt]; ~i; i nex[i]) {if(to[i] fa) continue;dfs(to[i], rt);dis[to[i]] dis[rt] value[i];}
}int main() {n read();int x, y, w;memset(head, -1, sizeof head);for(int i 1; i n; i) {x read(), y read(), w read();add(x, y, w);add(y, x, w);}dfs(1, 0);int u 0, v 0;for(int i 1; i n; i)if(dis[i] dis[u]) u i;memset(dis, 0, sizeof dis);dfs(u, 0);for(int i 1; i n; i)if(dis[i] dis[v]) v i;printf(%d %d %d\n, u, v, dis[v]);return 0;
}树的直径求解方法二
思路
以根节点出发去寻找到这个根节点的最长路以及次长路得到的两个节点就是树的直径的端点。如果我们要得到直径的数值还应该要做一次dfs因为我们一开始选定的根节点无法保证是不是在直径上。
代码
#include bits/stdc.husing namespace std;typedef long long ll;
const int N 1e5 10;int head[N], to[N], value[N], nex[N], cnt;
int n, ans, fir[N], sec[N], firnode[N], secnode[N];inline ll read() {ll x 1, s 0; char c;c getchar();while(c 0 || c 9) {if(c -) x -1;c getchar();}while(c 0 c 9) {s (s 1) (s 3) (c ^ 48);c getchar();}return x * s;
}void add(int x, int y, int w) {to[cnt] y;nex[cnt] head[x];value[cnt] w;head[x] cnt;
}void dfs(int rt, int fa) {firnode[rt] secnode[rt] rt;for(int i head[rt]; ~i; i nex[i]) {if(to[i] fa) continue;dfs(to[i], rt);if(fir[to[i]] value[i] fir[rt]) {//更新最长路sec[rt] fir[rt];fir[rt] fir[to[i]] value[i];firnode[rt] to[i];}else if(fir[to[i]] value[i] sec[rt]) {//更新次长路sec[rt] fir[to[i]] value[i];secnode[rt] to[i];}}
}int main() {n read();int x, y, w;memset(head, -1, sizeof head);for(int i 1; i n; i) {x read(), y read(), w read();add(x, y, w);add(y, x, w);}dfs(1, 0);printf(%d %d %d, firnode[1], secnode[1], fir[1] sec[1]);//假定我们选择的点是直径上的点。return 0;
}树的重心
思路
找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后生成的多棵树尽可能平衡。
树中所有点到某个点的距离和中到重心的距离和是最小的如果有两个距离和他们的距离和一样则这两个点都是重心
并且一棵树最多有两个重心且相邻。
因此我们可以通过dfs去记录每个节点的子树节点值然后去统计其最大结点数最小的节点。
代码
#include bits/stdc.husing namespace std;typedef long long ll;
const int N 1e5 10;int head[N], to[N], value[N], nex[N], cnt;
int n, ans, sz[N], maxn 0x3f3f3f3f, heart;inline ll read() {ll x 1, s 0; char c;c getchar();while(c 0 || c 9) {if(c -) x -1;c getchar();}while(c 0 c 9) {s (s 1) (s 3) (c ^ 48);c getchar();}return x * s;
}void add(int x, int y, int w) {to[cnt] y;nex[cnt] head[x];value[cnt] w;head[x] cnt;
}void dfs(int rt, int fa) {sz[rt] 1;int now_maxn 0;for(int i head[rt]; ~i; i nex[i]) {if(to[i] fa) continue;dfs(to[i], rt);sz[rt] sz[to[i]];if(sz[to[i]] now_maxn) now_maxn sz[to[i]];//记录最大子节点。}if(n - sz[rt] now_maxn) now_maxn n - sz[rt];//其父节点也算是他的子节点if(now_maxn maxn) heart rt, maxn now_maxn;
}int main() {n read();int x, y, w;memset(head, -1, sizeof head);for(int i 1; i n; i) {x read(), y read(), w read();add(x, y, w);add(y, x, w);}dfs(1, 0);printf(%d\n, heart);return 0;
}
