题面描述:
塔子哥想要对一批图片进行分类，依据它们之间的相似度矩阵进行处理。给定一个N∗N 的相似度矩阵，矩阵中的元素表示任意两张图片的相似度，若相似度大于 0，则认为两张图片相似；通过间接相似的方式，形成的相似类会将所有间接相似的图片归为一类。如果某张图片与其他图片均无相似度，则其自成一类。最终，要求输出每个相似类的相似度之和，并按从大到小的顺序排列。
思路
题意需要将相似的图片归为一类，很容易想到是并查集的解法，并查集也有路径压缩的方法，所以可以将相似度的和都存在集合的根节点上。
将所有相似的图片归类到一个集合中，并对图片矩阵a进行遍历，如果ai,j!=0，那么就获取其所在集合的根节点fa，使ans[fa]+=a[i][j]。为了防止重复计算，令a[i][j]=a[j][i]=0。
P14354.【并查集2】相似度计算
本题为2024年4月10日-华为暑期实习机考原题
华为机考的介绍点击这里
题目描述
小红想要处理一批图片，将相似的图片分类。他首先对图片的特征采样，得到图片之间的相似度，然后按照以下规则判断图片是否可以归为一类:
- 1)相似度>0表示两张图片相似;
- 2)如果A和B相似，B和C相似，但A和C不相似。那么认为A和C间接相似，可以把ABC归为一类，但不计算AC的相似度:
- 3)如果A和所有其他图片都不相似，则A自己归为一类，相似度为0。给定一个大小为N×N的矩阵M存储任意两张图片的相似度，M[i][j]即为第i个图片和第j个图片的相似度，请按照"从大到小"的顺序返回每个相似类中所有图片的相似度之和。
输入描述
第一行一个数N(1≤N≤900)，代表矩阵M中有N个图片。下面跟着N行，每行有N列数据，空格分隔(为了显示整齐，空格可能为多个)，代表N个图片之间的相似度。
其中0≤M[i][j]≤100，输入保证M[i][j]=M[j][i]
输入的矩阵分隔符为1个或多个连续空格
输出描述
每个相似类的相似度之和。格式为:一行数字，分隔符为1个空格
样例1
输入
5
0 0 50 0 0
0 0 0 25 0
50 0 0 0 15
0 25 0 0 0
0 0 15 0 0
输出
65 25
说明
把1~5看成A,B,C,D,E
矩阵显示，A和C相似度为50，C和E的相似度为15:B和D相似度为25。划分出2个相似类，分别为
1.{A,C,E}，相似度之和为65
2.{B,D}，相似度之和25
排序输出相似度之和，结果为:65 25
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
