描述：有N（N2+ (y_j-y_i)² + (z_j-z_i)²。請求出最大的t，使得N個網(wǎng)頁可以聚成K類，其中每個類至少包含一個網(wǎng)頁，且任意兩個位于不同類中網(wǎng)頁的相似度都至少為t。

輸入

第一行包含兩個整數(shù)N和K，后面N行每行三列，分別為x、y、z。

輸出

最大的t的值，使用四舍五入在小數(shù)點后保留六位小數(shù)。

樣例輸入

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;elser = mid;}printf("%.6lf\n", l);return 0; }

總結

以上是生活随笔為你收集整理的【2012百度之星/初赛下】B:网页聚类的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。