专业网站设计推荐,阿里巴巴国际贸易网站,wordpress微信公众号采集,全球跨境电商平台文章目录 重心实践题目小红的陡峭值 在树的算法中#xff0c;求解树的中心和重心是一类十分重要的算法
求解树的重心
树的重心的定义#xff1a;重心是树中的一个节点#xff0c;如果将这个点删除后#xff0c;剩余各个连通块中点数的最大值最小#xff0c;那么这个节点… 文章目录 重心实践题目小红的陡峭值 在树的算法中求解树的中心和重心是一类十分重要的算法
求解树的重心
树的重心的定义重心是树中的一个节点如果将这个点删除后剩余各个连通块中点数的最大值最小那么这个节点称为树的重心求解重心需要记录的值由于重心关注的是删除一个节点之后剩余的连通分支中点的最大值然后这个值要求是最小的然后需要返回这个最小化的最大值。删除一个节点之后会分为几个部分节点u的所有子树所独立出来的子树以及原本的树删除以u为根节点的树所以要记录u的所有子树当中size子树的最多节点数sumnunm以u为根节点的节点数(用于dfs的返回值)n-sumnum除去以u为根节点的剩余部分的节点数值得注意的是遍历的之后是从根节点到叶子节点但是我们是在归(叶子节点到根节点)中的过程中更新答案的由于是 无向图所以要么设置vis[i]标记节点是否访问过,要么设置dfs(u,fa)其中fa是u的父亲节点 c代码 int dfs(int u)
{vis[u] true; //为了不重复搜索所以得标记int size 0; // 记录u的子树中的最大节点数int sum 1; // 记录以u为根节点的子树的节点总数for(int i h[u];i!-1;ine[i]){int j e[i];if (vis[j]) continue;int s dfs(j);size max(size,s);sum s;}ans min(ans,max(size,n-sum));return sum;
}
python 代码
# 使用邻接表来存储点之间的边关系
g [[]*n ]
vis [False]*n
ans n
def dfs(u): global ansvis[u] Truesumnum 1 # 记录以u为根节点的子树的总节点数size 0 # 记录 u的子树当中最大的节点数for v in g[u]:if vis[v]: continue # 如果访问过就跳过s dfs(v) # 求解出以v为根节点的子树的节点数size max(size,s) # 更新答案sumnum s# 更新这个ansans min(ans,max(size,n-sumnum)) return sum
重心实践题目
小红的陡峭值
小红的陡峭值 这题与求解重心的思路十分相似都是删除一部分关注剩余的部分的情况不一样的是由于删除的是边所以只会将原本的树分为两个部分但是还是存在一个对应的关系
求解重心求解陡峭值总的值定点数n全部边的陡峭值esum删除的部分顶点边dfs返回的值以u为顶点的子树的总顶点数以u为顶点的子树的陡峭值关注的部分以u为顶点的子树当中顶点的最大数这个数目会被拿去更新ans并不关心以u为顶点的子树的陡峭值的最值而是对于每一个子树的情况都会拿去更新ans
import sys
sys.setrecursionlimit(10 ** 6)
n int(input())
g [[] for _ in range(n1)]# 类似于求解这个 重心的问题问题的关键在于从根到叶子同时在叶子返回这个根的时候动态更新答案
esum 0
for i in range(n-1):u,v map(int,input().split())g[u].append(v)g[v].append(u)esum abs(u-v)ans float(inf)
vis [False]*(n1)def dfs(u):global ansvis[u] True# 需要记录以u为根的陡峭值以及子树的陡峭值sumnum 0for v in g[u]:if vis[v]: continues dfs(v)sumnum abs(u-v) s # 更新答案ans min(abs(esum-abs(u-v)-s-s),ans)return sumnum
dfs(1)
print(ans)
