蓝桥杯|2021年第十二届蓝桥杯省赛第二场Python组（真题+解析+代码）（城邦）算法|职场和发展|图论|python

1 真题
文章图片

2 解析难度系数：???
考察题型：图论
涉及知识点：最小生成树-并查集

思路分析：
【蓝桥杯|2021年第十二届蓝桥杯省赛第二场Python组（真题+解析+代码）（城邦）】套用最小生成树模板-并查集。

3 代码

#模板-并查集 def root(x):#查找→根节点 if x!=p[x]: p[x]=root(p[x]) return p[x]def union(x,y):#合并←两节点 if root(x) != root(y): p[root(y)]=root(x)def cost(x,y):#计算权值 s=0 while x or y: if x%10 !=y%10: s+=x%10+y%10 x//=10 y//=10 return s #最小生成树 p=[i for i in range(2022)]#p:父节点列表 edge=[(i,j,cost(i,j)) for i in range(1,2022) for j in range(1,2022)]#生成边集合列表 edge.sort(key=lambda x:x[2])#sort:按权值升序排序 cnt,ans=0,0 for i in edge: if root(i[0])!=root(i[1]) and cnt<2020:#cnt：边数=最大顶点数-1 union(i[0],i[1]) ans+=i[2] cnt+=1 print(ans)#4046

参考链接：
Python之最小生成树 kruskal_m0_62277756的博客-CSDN博客
我写的是关于蓝桥杯的系列题解，感谢关注我的朋友们，我会持续输出高质量文章
蓝桥杯python组十二届省赛第二场真题+解析+代码（通俗易懂版）_编程有了思路-CSDN博客在 C/C++/Java/Python 等语言中，使用 % 表示求余，请问 2021%20 的值是多少？https://blog.csdn.net/m0_55148406/article/details/122790119