题目描述
小明想要处理一批图片，将相似的图片分类。他首先对图片的特征采样，得到图片之间的相似度，然后按照以下规则判断图片是否可以归为一类：
- 相似度 > 0 表示两张图片相似。
- 如果 A 和 B 相似，B 和 C 相似，但 A 和 C 不相似，那么认为 A 和 C 间接相似，可以把 A、B、C 归为一类，但不计算 A 和 C 的相似度。
- 如果 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 个空格。
用例输入
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 个相似类：
- {A, C, E}，相似度之和为 65
- {B, D}，相似度之和为 25
- 排序输出相似度之和，结果为：
65 25
解题思路
-
问题建模：
- 该问题可以看作是一个并查集问题，目标是将相似的图片归为一类。
- 使用并查集将直接相似和间接相似的图片合并为一个集合。
-
数据结构：
- 使用二维数组
mp存储图片之间的相似度。 - 使用数组
f存储并查集的父节点。 - 使用哈希表
res存储每个集合的相似度之和。
- 使用二维数组
-
并查集操作：
- 初始化并查集，每个图片自己是一个集合。
- 遍历相似度矩阵，如果两个图片相似，则将它们合并到同一个集合。
-
计算相似度：
- 遍历相似度矩阵，累加每个集合的相似度。
- 使用哈希表记录每个集合的相似度之和。
-
排序输出：
- 将所有集合的相似度之和存储到一个向量中，按从大到小排序。
- 输出排序后的结果。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
#include<string>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<set>
#include<list>
#include<sstream>
#include<bitset>
#include<stack>
#include<climits>
#include<iomanip>
#include<cstdint>
using namespace std;int mp[1005][1005]; // 存储图片之间的相似度
int f[1005]; // 并查集的父节点数组// 并查集查找根节点
int find(int root) {if (f[root] != root) {return f[root] = find(f[root]);}return root;
}// 并查集合并两个集合
void un(int x, int y) {if (find(x) == find(y)) return;f[x] = find(y);
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin >> n; // 输入图片数量for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {cin >> mp[i][j]; // 输入相似度矩阵}}for (int i = 0; i < n; i++) {f[i] = i; // 初始化并查集}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (mp[i][j]) { // 如果两个图片相似un(i, j); // 合并到同一个集合}}}map<int, int> res; // 存储每个集合的相似度之和for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (mp[i][j] && find(i) == find(j)) { // 如果两个图片相似且属于同一个集合int fl = find(i); // 找到集合的根节点res[fl] += mp[i][j]; // 累加相似度mp[i][j] = 0, mp[j][i] = 0; // 清除已计算的相似度}}}vector<int> res_v; // 存储所有集合的相似度之和for (auto& t : res) {res_v.push_back(t.second); // 添加到向量中}sort(res_v.begin(), res_v.end(), greater<int>()); // 按从大到小排序for (int i = 0; i < res_v.size() - 1; i++) {cout << res_v[i] << " "; // 输出每个集合的相似度之和}cout << res_v[res_v.size() - 1];return 0;
}
