题目 Single-link Clustering
Description Given n nodes in a two-dimensional space, we want to use single-link clustering method to find k clusters. This is equivalent to finding an MST (Minimum spanning tree) of these nodes and deleting k-1 longest edges. Your job is to output the length of the (k-1)-th longest edges of the MST.
Input There are multiple cases. For each case, the first line includes n and k (2<=k<=n<=100). The following n lines give the coordinates of n nodes. You may use Euclidean distance to measure the distance between two nodes.
Output For each case, output the length of the (k-1)-th longest edges. The precision is set to 2 digits after the decimal point.
Sample Input 6 2 1 1 2 1 1 2 3 3 4 2 4 3
Sample Output 2.24
// 这是一道single-link clustering的题目，然而根据所求（single-link clustering的spacing），题目中说明了可以用MST中得出答案 这很简单，只是prim算法有点遗忘，这是借这道题目第二次学习的一些感悟，以及一些更好理解的说法
思路
用prim算法求出mst，期间把所有mst的边记录下来，最后排序然后找到第k-1长的边即可
思路很简单，稍作解释，如果不知道single-link clustering 和mst的定义先自己百度 single-link clustering的spacing指的是各个簇之间的点的连线中最短的一个 如上图将点分为四个簇，spacing就是任意两个不同簇的点间的最短距离
然而恰好，若要把一些点聚类（single-link clustering法，还有很多高大上的聚类方法）， 只要求出它们的mst，去掉一个最长的边就分成两簇，再去掉第二长的就分成三簇，以此类推。
接着说prim，理解自然语言表示的算法！=理解代码写出来的算法 接下来直接从代码的角度描述算法（以邻接矩阵为存储的数据结构）
1、因为要用邻接矩阵来表示图，所以得先有一个邻接矩阵，直接输入或输入其他数据算出。 2、从一个点出发，把这个点作为已访问的部分，寻找与这个部分链接的最短的边，不断向外扩散。 3、期间要记录一个数据，很多网上的代码都把它叫做lowcost一类的，它是指未访问的部分中距离已访问的部分最短的边。（见下图） 4、还有个next点（或者minid或者min之类的叫法都有）的变量，用于表示接下来要访问的点。 5、每次循环做的事：在lowcost中寻找（第二层循环）距离已访问部分最短的边，更新next。 记录新的边的数据并根据next更新lowcost（因为多一个点，所以可能这个点到某个点的距离会比原来近） 6、初始化等简单的操作就好理解了，看代码吧。 (lowcost就是距离有红线连到的点（已访问）最近的点和已访问部分的距离，即V4，lowcost[4]=1)
#include <iostream> #include <algorithm> #include <iomanip> using namespace std; #define INF 1<<30//太大超过int会炸 #define MAX 101 double xs[MAX], ys[MAX],graph[MAX][MAX];//本题输入的是点的坐标 vector<double> mst_edges;//mst的边的长度 double get_graph(int a, int b) { return sqrt(pow(xs[a]-xs[b],2)+pow(ys[a]-ys[b],2)); }//求两点间距离 void prim(int n) { bool vers[MAX];//判断一个点是否访问过 double dis[MAX];//文章中的lowcost for (int i = 0; i < n; i++) { vers[i] = false; dis[i] = graph[0][i]; }//初始化 vers[0] = true;//将第一个点加入已访问的部分 for (int i = 1; i < n; i++) { int next = 0; double min = INF; for (int j = 1; j < n; j++) { if (!vers[j] && dis[j] < min) { min = dis[j]; next = j; }//找到下一个要访问得点 } vers[next] = true; mst_edges.push_back(min);//存储数据 for (int j = 0; j < n; j++) { if (graph[next][j]<dis[j]) dis[j] = graph[next][j];//更新dis } } } int main() { int n,k; while (cin >> n >> k) { mst_edges.clear(); for (int i = 0; i < n; i++) cin >> xs[i] >> ys[i]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) graph[i][j] = INF; for (int i = 0; i < n; i++) for (int j = i; j < n; j++) graph[i][j] = graph[j][i] = get_graph(i, j); prim(n); sort(mst_edges.begin(), mst_edges.end()); cout << fixed << setprecision(2) <<mst_edges[mst_edges.size()-k+1] << endl; } }