Python group in the second game of the 12th Landbridge cup in 2021 (true question + analysis + code): City State

1 The real question

2 analysis

The difficulty coefficient ：

Investigation question type ： graph theory

Knowledge points involved ： Minimum spanning tree - Union checking set

Thought analysis ：

Apply minimum spanning tree template - Union checking set .

3 Code

# Templates - Union checking set
def root(x):# lookup → The root node
if x!=p[x]:
p[x]=root(p[x])
return p[x]
def union(x,y):# Merge ← Two node
if root(x) != root(y):
p[root(y)]=root(x)
def cost(x,y):# Calculate weights
s=0
while x or y:
if x%10 !=y%10:
s+=x%10+y%10
x//=10
y//=10
return s
# Minimum spanning tree
p=[i for i in range(2022)]#p: List of parent nodes
edge=[(i,j,cost(i,j)) for i in range(1,2022) for j in range(1,2022)]# Generate a list of edge sets
edge.sort(key=lambda x:x[2])#sort: Sort in ascending order of weight
cnt,ans=0,0
for i in edge:
if root(i[0])!=root(i[1]) and cnt<2020:#cnt： Number of edges = Maximum number of vertices -1
union(i[0],i[1])
ans+=i[2]
cnt+=1
print(ans)#4046

Reference link ：

Python The smallest spanning tree of kruskal_m0_62277756 The blog of -CSDN Blog  

         I wrote a series of questions about the Blue Bridge Cup , Thank you for your attention , I will continue to output high-quality articles

Blue Bridge Cup python Real topic of the second game of the 12th provincial competition + analysis + Code （ Easy to understand version ）_ Programming has ideas -CSDN Blog stay C/C++/Java/Python Such as language , Use % To find the remainder , Excuse me, 2021%20 What's the value of ？https://blog.csdn.net/m0_55148406/article/details/122790119