描述:有N(N2+ (y_j-y_i)2 + (z_j-z_i)2。请求出最大的t,使得N个网页可以聚成K类,其中每个类至少包含一个网页,且任意两个位于不同类中网页的相似度都至少为t。
输入
第一行包含两个整数N和K,后面N行每行三列,分别为x、y、z。
输出
最大的t的值,使用四舍五入在小数点后保留六位小数。
样例输入
5 3
0.1 0.2 0.4
0.2 0.8 0.7
0.3 0.4 0.5
0.0 0.5 0.0
0.3 0.3 0.2
样例输出
0.170000
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
const int MAXN = 2010;
const double EPS = 1e-8;
double x[MAXN], y[MAXN], z[MAXN], d[MAXN][MAXN];
bool vis[MAXN];
int n, k, cnt, belong[MAXN];
queue <int> q;
vector <int> e[MAXN];
vector <int> :: iterator iter;
double dist(int i, int j)
{
return (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) + (z[i] - z[j]) * (z[i] - z[j]);
}
void bfs(int p)
{
memset(vis , 0 , sizeof(vis));
q.push(p);
while (!q.empty())
{
int u = q.front();
q.pop();
belong[u] = cnt, vis[u] = true;
for(iter = e[u].begin(); iter != e[u].end(); ++iter)
{
if (!vis[*iter])
q.push(*iter);
}
}
}
bool check(double t)
{
int i, j;
for (i = 0; i < n; ++i)
{
e[i].clear();
for (j = 0; j < n; ++j)
{
if (d[i][j] < t && i != j)
{
e[i].push_back(j);
}
}
}
cnt = 0;
for (i = 0; i < n; ++i)
{
if (!belong[i])
{
cnt++;
bfs(i);
}
}
return cnt >= k;
}
int main(void)
{
int i, j;
scanf("%d %d", &n, &k);
for (i = 0; i < n; ++i)
{
scanf("%lf %lf %lf", &x[i], &y[i], &z[i]);
}
for (i = 0; i < n; ++i)
{
for (j = 0; j < n; ++j)
{
d[i][j] = dist(i, j);
}
}
double l = 0, r = 3;
while (r - l > EPS)
{
memset(belong , 0 , sizeof(belong));
double mid = (l + r) / 2;
if( check(mid) )
l = mid;
else
r = mid;
}
printf("%.6lf\n", l);
return 0;
}
分享到:
相关推荐
代码实操:Python聚类分析 SKLean中有专门的聚类库:cluster,其包含了很多的聚类算法。 本例将使用一份无标签的数据集做聚类分析,以得到不同类别的特征和分布状态等。 对于聚类模型结果的评估,主要考虑如下三...
MATLAB 绘图复刻三:分层聚类分析图
BIRCH:使用聚类特征树的多阶段聚类.pdf 学习资料 复习资料 教学资源
SPSS 16实用教程:08 聚类分析与判别分析.ppt
使用 isodata 聚类算法来确定多维属性空间中像元自然分组的特征并将结果存储在输出 ASCII 特征文件中。
⽅法⼀:直接聚类, ⽅法⼀:直接聚类 利⽤clusterdata函数对样本数据进⾏⼀次聚类,其缺点为可供⽤户选择的⾯较窄,不能更改距离的计算⽅法,该⽅法的使⽤者⽆需了解聚类的原理和过程,但是聚类效果受限制。...
模糊聚类关键词:模糊聚类,半监督介绍本开源项目为模糊聚类算法python代码,主要算法包括: FCM(模糊C均值算法) MEC(极大熵模糊聚类算法) 核模糊聚类算法SFCM(半监督模糊聚类算法) eSFCM(基于信息熵的半监督...
故障诊断论文:基于聚类分析的卫星姿态控制系统故障诊断方法研究.doc
基于项目提供的汽车相关数据,通过聚类分析的方法实现汽车产品聚类,以构建汽车产品画像、分析产品定位、完成汽车竞品分析等要求。 2. 项目数据 项目提供的汽车数据包括26个字段共205条数据,数据文件为“car_price...
(1) 标准数字 在工具条中按下【标准数字聚类】按钮后,选择工具条上提供的各种标准数字。在左视图就会得到多个标准数字。 每行中存放的标准数字个数与blank.bmp文件大小有关,读者可以自行修改该文件的...
名称:DPC聚类算法 功能:聚类数据集 类别:密度聚类算法
名称:AP聚类算法 功能:聚类数据集 类别:新聚类算法
Witten和Tibshirani(2010)的稀疏聚类方法的Python实现。 演示结果 每个样本都具有1000个功能,其中1%具有参考价值。 层次聚类 稀疏层次聚类 职能 稀疏层次聚类 稀疏KMeans聚类 稀疏层次聚类的转弯参数选择 稀疏...
2.6:聚类分析—层次聚类法.do
2.5.1:聚类分析—快速聚类法.do
#资源达人分享计划#
模式识别ISODATA聚类分析算法演示程序 程序可以绘制二维坐标显示样本点,可以添加、删除、编辑、导入样本点数据,可以生成随机测试数据。可以生成查看日志文件,能够选择手动修改还是自动修改参数等,对于二维数据...
2.5.2:聚类分析—快速聚类法——中位数.do
https://blog.csdn.net/weixin_46098577/article/details/116129817