本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P5536 【XR-3】核心城市 - 洛谷【题目描述】X 国有n nn座城市n − 1 n - 1n−1条长度为1 11的道路每条道路连接两座城市且任意两座城市都能通过若干条道路相互到达显然城市和道路形成了一棵树。X 国国王决定将k kk座城市钦定为 X 国的核心城市其余城市为非核心城市。这k kk座核心城市需满足以下两个条件这k kk座城市可以通过道路在不经过非核心城市的情况下两两相互到达。定义某个非核心城市与这k kk座核心城市的距离为这座城市与k kk座核心城市的距离的最小值。为了衡量交通状况国王发明了交通拥堵度它为所有非核心城市与核心城市的距离中的最大值。问题来了如何安排核心城市才能使交通拥堵度最小呢请输出满足条件的最小交通拥堵度。【输入】第一行2 22个正整数n , k n,kn,k。接下来n − 1 n - 1n−1行每行2 22个正整数u , v u,vu,v表示第u uu座城市与第v vv座城市之间有一条长度为1 11的道路。【输出】一行一个整数表示满足条件的最小交通拥堵度。【输入样例】6 3 1 2 2 3 2 4 1 5 5 6【输出样例】1【解题思路】【算法标签】#普及plus #树形DP【代码详解】#includebits/stdc.husingnamespacestd;constintN100005,M2*N;intn,k,st,ed,t,maxx,root;// n: 节点数k: 选择的节点数st: 直径一端ed: 直径另一端t: 临时节点maxx: 最大深度root: 树的中心inth[N],e[M],ne[M],idx;// 邻接表存储树intdeep[N],max_deep[N];// deep: 节点深度max_deep: 子树最大深度introuter[N],tmp[N],ans[N];// router: 直径路径tmp: 临时路径ans: 每个节点为根的子树最大深度// 添加无向边voidadd(inta,intb){e[idx]b;ne[idx]h[a];h[a]idx;}// 第一次DFS求树的直径的一端voiddfs_1(intu,intfa){deep[u]deep[fa]1;// 计算节点深度if(deep[u]maxx)// 更新最大深度{maxxdeep[u];tu;// 记录最深节点}for(intih[u];i!-1;ine[i])// 遍历所有邻接点{intve[i];if(vfa)// 跳过父节点continue;dfs_1(v,u);}}// 第二次DFS求直径路径voiddfs_2(intu,intfa,intstep){if(ued)// 如果到达直径的另一端{memcpy(router,tmp,sizeof(router));// 复制路径}for(intih[u];i!-1;ine[i])// 遍历所有邻接点{intve[i];if(vfa)// 跳过父节点continue;tmp[step1]v;// 记录路径dfs_2(v,u,step1);}}// 第三次DFS计算每个节点的最大深度和ans值voiddfs_3(intu,intfa){deep[u]deep[fa]1;// 计算节点深度max_deep[u]deep[u];// 初始化最大深度为当前深度for(intih[u];i!-1;ine[i])// 遍历所有邻接点{intve[i];if(vfa)// 跳过父节点continue;dfs_3(v,u);max_deep[u]max(max_deep[u],max_deep[v]);// 更新子树最大深度}ans[u]max_deep[u]-deep[u]1;// 计算以u为根的子树高度}intmain(){cinnk;// 输入节点数和选择的节点数memset(h,-1,sizeof(h));// 初始化邻接表for(inti1;in;i)// 输入n-1条边{intu,v;cinuv;add(u,v),add(v,u);// 添加无向边}tmaxx0;dfs_1(1,0);// 第一次DFS找到直径一端stt;// 直径起点tmaxx0;dfs_1(st,0);// 第二次DFS找到直径另一端edt;// 直径终点tmp[0]st;// 初始化路径起点dfs_2(st,0,0);// 寻找直径路径rootrouter[maxx/2];// 找到树的中心直径中点memset(deep,0,sizeof(deep));dfs_3(root,0);// 第三次DFS计算每个节点的ans值sort(ans1,ansn1,greaterint());// 将ans从大到小排序coutans[k1]endl;// 输出第k1大的值return0;}【运行结果】6 3 1 2 2 3 2 4 1 5 5 6 1
题解：洛谷 P5536 【XR-3】核心城市
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P5536 【XR-3】核心城市 - 洛谷【题目描述】X 国有n nn座城市n − 1 n - 1n−1条长度为1 11的道路每条道路连接两座城市且任意两座城市都能通过若干条道路相互到达显然城市和道路形成了一棵树。X 国国王决定将k kk座城市钦定为 X 国的核心城市其余城市为非核心城市。这k kk座核心城市需满足以下两个条件这k kk座城市可以通过道路在不经过非核心城市的情况下两两相互到达。定义某个非核心城市与这k kk座核心城市的距离为这座城市与k kk座核心城市的距离的最小值。为了衡量交通状况国王发明了交通拥堵度它为所有非核心城市与核心城市的距离中的最大值。问题来了如何安排核心城市才能使交通拥堵度最小呢请输出满足条件的最小交通拥堵度。【输入】第一行2 22个正整数n , k n,kn,k。接下来n − 1 n - 1n−1行每行2 22个正整数u , v u,vu,v表示第u uu座城市与第v vv座城市之间有一条长度为1 11的道路。【输出】一行一个整数表示满足条件的最小交通拥堵度。【输入样例】6 3 1 2 2 3 2 4 1 5 5 6【输出样例】1【解题思路】【算法标签】#普及plus #树形DP【代码详解】#includebits/stdc.husingnamespacestd;constintN100005,M2*N;intn,k,st,ed,t,maxx,root;// n: 节点数k: 选择的节点数st: 直径一端ed: 直径另一端t: 临时节点maxx: 最大深度root: 树的中心inth[N],e[M],ne[M],idx;// 邻接表存储树intdeep[N],max_deep[N];// deep: 节点深度max_deep: 子树最大深度introuter[N],tmp[N],ans[N];// router: 直径路径tmp: 临时路径ans: 每个节点为根的子树最大深度// 添加无向边voidadd(inta,intb){e[idx]b;ne[idx]h[a];h[a]idx;}// 第一次DFS求树的直径的一端voiddfs_1(intu,intfa){deep[u]deep[fa]1;// 计算节点深度if(deep[u]maxx)// 更新最大深度{maxxdeep[u];tu;// 记录最深节点}for(intih[u];i!-1;ine[i])// 遍历所有邻接点{intve[i];if(vfa)// 跳过父节点continue;dfs_1(v,u);}}// 第二次DFS求直径路径voiddfs_2(intu,intfa,intstep){if(ued)// 如果到达直径的另一端{memcpy(router,tmp,sizeof(router));// 复制路径}for(intih[u];i!-1;ine[i])// 遍历所有邻接点{intve[i];if(vfa)// 跳过父节点continue;tmp[step1]v;// 记录路径dfs_2(v,u,step1);}}// 第三次DFS计算每个节点的最大深度和ans值voiddfs_3(intu,intfa){deep[u]deep[fa]1;// 计算节点深度max_deep[u]deep[u];// 初始化最大深度为当前深度for(intih[u];i!-1;ine[i])// 遍历所有邻接点{intve[i];if(vfa)// 跳过父节点continue;dfs_3(v,u);max_deep[u]max(max_deep[u],max_deep[v]);// 更新子树最大深度}ans[u]max_deep[u]-deep[u]1;// 计算以u为根的子树高度}intmain(){cinnk;// 输入节点数和选择的节点数memset(h,-1,sizeof(h));// 初始化邻接表for(inti1;in;i)// 输入n-1条边{intu,v;cinuv;add(u,v),add(v,u);// 添加无向边}tmaxx0;dfs_1(1,0);// 第一次DFS找到直径一端stt;// 直径起点tmaxx0;dfs_1(st,0);// 第二次DFS找到直径另一端edt;// 直径终点tmp[0]st;// 初始化路径起点dfs_2(st,0,0);// 寻找直径路径rootrouter[maxx/2];// 找到树的中心直径中点memset(deep,0,sizeof(deep));dfs_3(root,0);// 第三次DFS计算每个节点的ans值sort(ans1,ansn1,greaterint());// 将ans从大到小排序coutans[k1]endl;// 输出第k1大的值return0;}【运行结果】6 3 1 2 2 3 2 4 1 5 5 6 1
