题面描述:

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

思路

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

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

最后对$ans$进行排序，再倒序输出即可。

代码步骤

1. 初始化并查集：每张图片自成一类，初始化时将每张图片的父节点指向自己。
2. 构建相似度关系：遍历相似度矩阵，如果两张图片的相似度大于 0，则将它们合并到同一个集合中。
3. 计算相似度之和：在合并过程中，我们将相似度的和累加到根节点的相似度和数组中。为了避免重复计算，合并后将对应的相似度值置为 0。
4. 输出结果：最后，对相似度之和进行排序，并输出时按从大到小的顺序。

代码注释解析

1. 数据结构定义：

   • a[1000][1000] 用于存储相似度矩阵。
   • fa[1000] 用于记录每个节点的父节点，构建并查集。
   • ans[1000] 用于存储每个相似类的相似度之和。

2. 路径压缩的查找函数：

   • find(int x) 函数使用路径压缩来提高查找效率。

3. 合并过程：

   • 在读取相似度矩阵时，如果发现相似度不为 0，则合并对应的两张图片。

4. 相似度和的计算：

   • 遍历相似度矩阵，如果两个图片属于同一类，就将其相似度累加到对应的根节点。

5. 结果输出：

   • 对相似度和进行排序，并倒序输出，确保从大到小排列。

代码

C++

#include <bits/stdc++.h>
using namespace std;

int n;                     // 图片数量
int a[1000][1000];        // 相似度矩阵
int fa[1000];             // 并查集的父节点
int ans[1000];            // 每个相似类的相似度之和

// 查找函数，带路径压缩
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int main() {
    std::ios::sync_with_stdio(false);
    cin >> n;

    // 初始化并查集
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;         // 每个节点的父节点指向自己
    }

    // 读取相似度矩阵并构建并查集
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> a[i][j];
            if (a[i][j] != 0) {
                int fax = find(i), fay = find(j); // 找到各自的根节点
                if (fax != fay) {
                    fa[fax] = fay;  // 合并两个集合
                }
            }
        }
    }

    // 计算每个相似类的相似度之和
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (a[i][j] && find(i) == find(j)) { // 如果存在相似度并且属于同一类
                ans[find(i)] += a[i][j]; // 将相似度累加到根节点的相似度和中
                a[i][j] = 0;              // 为防止重复计算，将相似度置为0
                a[j][i] = 0;              // 对称位置也置为0
            }
        }
    }
    for(int i = 1; i <= n; i++){
        if(find(i) != i)ans[i] = -1;
    }
    // 输出相似度之和，先排序
    sort(ans + 1, ans + n + 1);
    for (int i = n; i > 0; --i) { // 倒序输出
        if(ans[i] == -1)break;
        cout << ans[i] << " ";
    }

    return 0;
}

python

# 并查集类定义
class UnionFind:
    def __init__(self, n):
        self.fa = list(range(n + 1))  # 初始化父节点

    def find(self, x):
        if x != self.fa[x]:
            self.fa[x] = self.find(self.fa[x])  # 路径压缩
        return self.fa[x]

def main():
    n = int(input().strip())  # 读取图片数量
    a = [list(map(int, input().strip().split())) for _ in range(n)]  # 读取相似度矩阵
    uf = UnionFind(n)  # 创建并查集实例
    ans = [0] * (n + 1)  # 每个相似类的相似度之和

    # 读取相似度矩阵并构建并查集
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if a[i - 1][j - 1] != 0:  # 注意索引从0开始
                fax = uf.find(i)  # 找到第i个图片的根节点
                fay = uf.find(j)  # 找到第j个图片的根节点
                if fax != fay:
                    uf.fa[fax] = fay  # 合并两个集合

    # 计算每个相似类的相似度之和
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if a[i - 1][j - 1] != 0 and uf.find(i) == uf.find(j):
                ans[uf.find(i)] += a[i - 1][j - 1]  # 将相似度累加到根节点的相似度和中
                a[i - 1][j - 1] = 0  # 为防止重复计算，将相似度置为0
                a[j - 1][i - 1] = 0  # 对称位置也置为0
    for i in range(1,n+1):
        if uf.find(i) != i:
            ans[i] = -1
    # 输出相似度之和，先排序
    sorted_ans = sorted(ans[1:], reverse=True)  # 排序并去掉第0个元素
    for score in sorted_ans:
        if score == -1:
            break
        print(score, end=' ')  # 打印相似度和

if __name__ == "__main__":
    main()

java

import java.util.*;

public class Main {
    static class UnionFind {
        int[] fa;

        public UnionFind(int n) {
            fa = new int[n + 1]; // 初始化父节点数组
            for (int i = 0; i <= n; i++) {
                fa[i] = i;
            }
        }

        public int find(int x) {
            if (fa[x] != x) {
                fa[x] = find(fa[x]); // 路径压缩
            }
            return fa[x];
        }

        public void union(int x, int y) {
            int fax = find(x);
            int fay = find(y);
            if (fax != fay) {
                fa[fax] = fay; // 合并集合
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine()); // 读取图片数量
        int[][] a = new int[n][n]; // 相似度矩阵
        for (int i = 0; i < n; i++) {
            String[] line = scanner.nextLine().split(" ");
            for (int j = 0; j < n; j++) {
                a[i][j] = Integer.parseInt(line[j]);
            }
        }
        
        UnionFind uf = new UnionFind(n);
        int[] ans = new int[n + 1]; // 每个相似类的相似度之和

        // 读取相似度矩阵并构建并查集
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (a[i - 1][j - 1] != 0) { // 注意索引从 0 开始
                    uf.union(i, j);
                }
            }
        }

        // 计算每个相似类的相似度之和
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (a[i - 1][j - 1] != 0 && uf.find(i) == uf.find(j)) {
                    ans[uf.find(i)] += a[i - 1][j - 1];
                    a[i - 1][j - 1] = 0; // 避免重复计算
                    a[j - 1][i - 1] = 0;
                }
            }
        }
        for(int i = 1; i <= n; i++){
            if(uf.find(i) != i)ans[i] = -1;
        }
        // 排序并输出
        List<Integer> sortedList = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if(ans[i] == -1)continue;
            sortedList.add(ans[i]);
        }
        sortedList.sort(Collections.reverseOrder()); // 按降序排序

        for (int score : sortedList) {
            System.out.print(score + " ");
        }
        scanner.close();
    }
}

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

华为机考的介绍点击这里

题目描述

小红想要处理一批图片，将相似的图片分类。他首先对图片的特征采样，得到图片之间的相似度，然后按照以下规则判断图片是否可以归为一类:

• 1)相似度>0表示两张图片相似;
• 2)如果A和B相似，B和C相似，但A和C不相似。那么认为A和C间接相似，可以把ABC归为一类，但不计算AC的相似度:
• 3)如果A和所有其他图片都不相似，则A自己归为一类，相似度为0。给定一个大小为$N\times N$的矩阵$M$存储任意两张图片的相似度，M[i][j]即为第$i$个图片和第$j$个图片的相似度，请按照"从大到小"的顺序返回每个相似类中所有图片的相似度之和。

输入描述

第一行一个数$N(1\le N\le 900)$，代表矩阵$M$中有$N$个图片。下面跟着$N$行，每行有$N$列数据，空格分隔(为了显示整齐，空格可能为多个)，代表$N$个图片之间的相似度。

其中$0\le M[i][j]\le 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