考的是简单的并查集
这道题考法就是并查集，若两个图片相似度大于0，则将他们放到一个家族中，同时维护家族的相似度总和。
注意 M 矩阵是对称矩阵，所以需要避免重复维护相似度，因此可以只针对 M 矩阵的下三角矩阵或上三角矩阵中的连接块，计算相似度总和；或考虑整个 M 矩阵，然后相似度总和除以2。
代码如下：
#include<iostream>
#include<unordered_set>
#include<vector>
#include<algorithm>
using namespace std;const int N = 910;int f[N], sum[N] , M[N][N];int find(int x){if(x != f[x]) f[x] = find(f[x]);return f[x];
}bool cmp(int x,int y){return x > y;
}int main(){unordered_set<int> Set;vector<int> v;int n ;cin >> n ;for(int i = 1 ; i <= n ; i ++) {f[i] = i;sum[i] = 0;}for(int i = 1 ; i <= n ; i ++){for(int j = 1 ; j <= n ; j ++){scanf("%d",&M[i][j]);}}for(int i = 1 ; i <= n ; i ++){for(int j = 1 ; j <= i ; j ++){if(M[i][j]) {int t = sum[find(i)] + M[i][j];f[find(i)] = find(j);sum[find(i)] += t;}}}for(int i = 1 ; i <= n ; i ++) Set.insert(sum[find(i)]);for(auto it: Set) v.push_back(it);sort(v.begin(),v.end(),cmp);for(int i = 0 ; i < v.size() ; i ++) printf("%d ",v[i]);return 0;
}
