本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1547 [USACO05MAR] Out of Hay S - 洛谷【题目描述】Bessie 计划调查N NN2 ≤ N ≤ 2 000 2 \leq N \leq 2\,0002≤N≤2000个农场的干草情况它从1 11号农场出发。农场之间总共有M MM1 ≤ M ≤ 10 4 1 \leq M \leq 10^41≤M≤104条双向道路所有道路的总长度不超过10 9 10^9109。有些农场之间存在着多条道路所有的农场之间都是连通的。Bessie 希望计算出该图中最小生成树中的最长边的长度。【输入】第一行两个整数N , M N,MN,M。接下来M MM行每行三个用空格隔开的整数A i , B i , L i A_i,B_i,L_iAi​,Bi​,Li​表示A i , B i A_i,B_iAi​,Bi​之间有一条道路长度为L i L_iLi​。【输出】一个整数表示最小生成树中的最长边的长度。【输入样例】3 3 1 2 23 2 3 1000 1 3 43【输出样例】43【核心思想】问题分析给定N NN个农场、M MM条双向道路的无向连通图求最小生成树MST中的最长边长度。这是一个最小生成树 边权追踪问题关键在于利用 Kruskal 算法按边权从小到大选边自然保证最后加入的边即为 MST 中的最大边。算法选择Kruskal 算法按边权升序排序用并查集维护连通性每次选择不形成环的最小边最大边追踪在 Kruskal 过程中每次成功加入生成树时更新maxn max(maxn, w)最终maxn即为 MST 的最长边关键步骤读取输入读入N , M N, MN,M和M MM条边( A i , B i , L i ) (A_i, B_i, L_i)(Ai​,Bi​,Li​)边排序按边权w ww从小到大排序并查集初始化p [ i ] i p[i] ip[i]ii ii从1 11到N NNKruskal 选边遍历排序后的边查找a f i n d ( A i ) a find(A_i)afind(Ai​)b f i n d ( B i ) b find(B_i)bfind(Bi​)若a ≠ b a \neq bab不连通合并p [ a ] b p[a] bp[a]b更新最大边权maxn max(maxn, w)输出maxn时间/空间复杂度时间复杂度O ( M log ⁡ M M ⋅ α ( N ) ) O(M \log M M \cdot \alpha(N))O(MlogMM⋅α(N))排序O ( M log ⁡ M ) O(M \log M)O(MlogM)并查集操作近似O ( 1 ) O(1)O(1)空间复杂度O ( N M ) O(N M)O(NM)并查集 边数组Kruskal 的核心思想贪心选边按边权从小到大依次选择若该边连接两个不同连通块则加入 MST。由于边权递增最后加入的边必然是当前可选的最大边即为 MST 的最长边并查集维护连通性路径压缩 按秩合并保证近乎常数时间的连通性判断MST 性质Kruskal 的正确性基于割性质——全局最小边必在某棵 MST 中按序选边保证不遗漏更优解适用于无向图最小生成树 追踪特定边权类问题核心是按权排序后用并查集贪心选边【算法标签】#普及 #生成树【代码详解】#includebits/stdc.husingnamespacestd;constintN2005,M10005*2;intn,m,ans,p[N],maxn-1;// n: 节点数, m: 边数, maxn: 最大边权structEdge// 存储边{inta,b,w;// 起点, 终点, 边权booloperator(constEdgeE)const// 按边权从小到大排序{returnwE.w;}}edges[M];intfind(intx)// 并查集查找{if(p[x]!x){p[x]find(p[x]);}returnp[x];}voidkruskal()// Kruskal算法{sort(edges1,edgesm1);// 边按权值排序for(inti1;in;i)// 初始化并查集{p[i]i;}intres0;// 总权值for(inti1;im;i)// 遍历所有边{intaedges[i].a,bedges[i].b,wedges[i].w;afind(a),bfind(b);if(a!b)// 不连通加入生成树{p[a]b;// 合并resw;// 累加权值maxnmax(maxn,w);// 更新最大边权}}}intmain(){cinnm;// 输入节点数和边数for(inti1;im;i)// 输入边{inta,b,w;cinabw;edges[i]{a,b,w};}kruskal();// 计算最小生成树coutmaxnendl;// 输出最大边权return0;}【运行结果】3 3 1 2 23 2 3 1000 1 3 43 43