上海部道网站 建设,广告设计公司vi设计,什么网站可以做ui兼职,东莞网站建设方案表题目描述#xff1a;
小明想要处理一批图片#xff0c;将相似的图片分类#xff0c;他首先对图片的特征采样#xff0c;得到图片之间的相似度#xff0c;然后 按照以下规则判断图片是否可以归为一类#xff1a; 1#xff09;相似度0表示两张图片相似#xff1b; 2…题目描述
小明想要处理一批图片将相似的图片分类他首先对图片的特征采样得到图片之间的相似度然后 按照以下规则判断图片是否可以归为一类 1相似度0表示两张图片相似 2如果A和B相似B和C相似但A和C不相似那么认为A和C间接相似可以把ABC归为一类但不计算AC的相似度 3如果A和所有其他图片都不相似则A自己归为一类相似度为0。 给定一个大小为N×N的矩阵M存储任意两张图片的相似度M[i][j]即为第i个图片和第j个图片的相似度请按照“从大到小”的顺序返回每个相似类 中所有图片的相似度之和。
输入描述
第一行为一个整数N代表矩阵M中有N个图片。下面跟着N行每行有N列数据空格分隔为了显示整齐空格可能为多个代表N个图片之间的相似度。 约束
0 N 9000 M[i][j] 100输入保证 M[i][i]0,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 输出 62 25 样例2 输入 5 0 5 42 0 0 5 0 0 91 0 42 0 0 0 15 0 91 0 0 0 0 0 15 0 0 输出 153 样例3 输入 7 0 1 3 0 0 0 0 1 0 2 0 0 0 0 3 2 0 0 0 0 0 0 0 0 0 3 0 9 0 0 0 3 0 5 0 0 0 0 0 5 0 7 0 0 0 9 0 7 0 输出 24 6 AC代码
#include bits/stdc.h
using namespace std;
const int N 1010;int n, m;
int k[N][N];
int p[N];
mapint, int p2;
mapint, bool p3;
vectorint res;int find(int x)
{if(p[x] ! x) p[x] find(p[x]);return p[x];
}int main()
{cin n;for(int i 1; i n; i ) p[i] i;for(int i 1; i n; i ){for(int j 1; j n; j ){cin k[i][j];if(k[i][j] 0) p[find(i)] find(j);}}for(int i 1; i n; i ){for(int j 1; j n; j ){if(find(i) find(j) k[i][j] 0) p2[find(i)] k[i][j];}}for(int i 1; i n; i ){if(p3[find(i)] false){res.push_back(p2[find(i)] / 2);p3[find(i)] true;}}sort(res.begin(), res.end());reverse(res.begin(), res.end());for(int i 0; i res.size(); i ){if(i ! res.size() - 1) cout res[i] ;else cout res[i];}return 0;
}
