题目

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

1)相似度>0表示两张图片相似，

2)如果A和B相似，B和C相似，但A和C不相似。那么认为A和C间接相似，可以把ABC归为一类，但不计算AC的相似度

3)如果A和所有其他图片都不相似，则A自己归为一类，相似度为0.给定一个大小为NxN的矩阵M存储任意两张图片的相似度，M[i][j]即为第i个图片和第j个图片的相似度，请按照”从大到小”的顺序返回每个相似类中所有图片的相似度之和。

约束：
1.0<N<=900
2.0<=M[i][j]<=100,输入保证M[i][i] =0,M[i][j]=M[j][i]

点评：考虑到该题是将联通分量合并并求各自树的权值和，所以可以采用并查集的方法。

import java.io.*;
import java.util.*;

public class Main{
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    static int N = 910;
    static int[][] w = new int[N][N];
    static int[] p = new int[N];
    static int[] score = new int[N];
    static List<Integer> ans = new ArrayList<>();

    public static int nextInt()throws IOException{
        in.nextToken();
        return (int)in.nval;
    }

    public static int find(int x){
        if(x!=p[x]) p[x] = find(p[x]);
        return p[x];
    }

    public static void main(String[] args)throws IOException{
        int n = nextInt();
        for(int i=1; i<=n; i++) p[i] = i;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                w[i][j] = nextInt();
            }
        }
        for(int i=1; i<=n; i++){
            for(int j=i+1; j<=n; j++){
                if(w[i][j]==0) continue;
                int pa = find(i), pb = find(j);
                if(pa!=pb){
                    p[pa] = pb;
                    score[pb] = score[pa]+w[i][j];
                }else score[pa] += w[i][j];
            }
        }
        for(int i=1; i<=n; i++){
            if(p[i]==i) ans.add(score[i]);
        }
        Collections.sort(ans);
        Collections.reverse(ans);
        for(Integer i : ans) out.print(i+" ");
        out.flush();
        out.close();
    }
}

class PII{
    String name;
    int age;
    public PII(String name, int age){
        this.name = name;
        this.age = age;
    }
    @Override
    public boolean equals(Object o){
        if(this == o) return true;
        if(!(o instanceof PII)) return false;
        PII that = (PII)o;
        return this.name.equals(that.name) && this.age == that.age;
    }
    @Override
    public int hashCode(){
        return Objects.hash(name, age);
    }
}

输入

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