题目内容

小红打算把若干图片做归组，把彼此接近的图分到同一集合。她先抽取各图特征并据此量出两两接近程度，再依下列几条判定可否并进同一集合:

• 1)两图接近程度若大于$0$，就视为彼此接近;
• 2)倘若$U$与$V$接近、$V$与$W$接近，哪怕$U$与$W$并不接近，也把$U$、$W$看成借由中间图间接接近，于是$UVW$可并进同一集合，只是$UW$那对接近程度不加进总和;
• 3)倘若$U$跟其余各图全不接近，就把$U$单独成组，该组接近程度记作$0$。现给出尺寸为$K\times K$的表$G$用来记下任意两图的接近程度，$G[p][q]$表示序号$p$那幅与序号$q$那幅的接近程度，请依由大至小的次序给出每个接近组内全部图片接近程度的总和。

输入描述

首行给出整数$K(1\le K\le 900)$，表示表$G$对应着$K$幅图片。随后连续$K$行，一行$K$个数，彼此用空格隔开(为排版整齐，空格个数可以不止一个)，记载这$K$幅图两两的接近程度。

其中$0\le G[p][q]\le 100$，数据保证$G[p][q]=G[q][p]$

该表各项之间的分隔由连续$1$个或更多空格构成

输出描述

各个接近组的接近程度总和。写法是:同一行若干个数，彼此用$1$个空格隔开

样例1

输入

5
0 0 0 33 0
0 0 14 0 0
0 14 0 0 0
33 0 0 0 6
0 0 0 6 0

输出

39 14

说明

把$1$至$5$依次记成$U,V,W,X,Y$
由表可知，$U$与$X$接近程度为$33$，$X$与$Y$接近程度为$6$；$V$与$W$接近程度为$14$。于是得到$2$个接近组，分别是
1.{$U,X,Y$}，接近程度合计$39$
2.{$V,W$}，接近程度合计$14$
按从大到小排出这些合计，得到:$39$ $14$

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写