本题为2024年4月10日-华为暑期实习机考原题

华为机考的介绍点击这里

题目描述

题面描述:

塔子哥想要对一批图片进行分类，依据它们之间的相似度矩阵进行处理。给定一个$N*N$ 的相似度矩阵，矩阵中的元素表示任意两张图片的相似度，若相似度大于 0，则认为两张图片相似；通过间接相似的方式，形成的相似类会将所有间接相似的图片归为一类。如果某张图片与其他图片均无相似度，则其自成一类。最终，要求输出每个相似类的相似度之和，并按从大到小的顺序排列。

思路

题意需要将相似的图片归为一类，很容易想到是并查集的解法，并查集也有路径压缩的方法，所以可以将相似度的和都存在集合的根节点上。

将所有相似的图片归类到一个集合中，并对图片矩阵$a$进行遍历，如果$a_{i,j}!=0$，那么就获取其所在集合的根节点$fa$，使$ans[fa]+=a[i][j]$。为了防止重复计算，令$a[i][j]=a[j][i]=0$。