最小生成树：一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。最小生成树可 以用kruskal（克鲁斯卡尔）算法或Prim（普里姆）算法求出。
思路：
1.审题，把题目要求的边都筛选出来
2.对边排序
3.用并查集连边
4.判断有几根节点
在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即）且为无循环图，使得
的 w(T) 最小，则此 T 为 G 的最小生成树。
最小生成树其实是最小权重生成树的简称。
许多应用问题都是一个求无向连通图的最小生成树问题。例如：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同；另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。
例题：/* 给出n个点，要求距离小于10或大于1000不能建边，问联通这些点至少需要的距离 不存在输出-1 */
代码实现：
#include<cstdio> #include<vector> #include<cmath> #include<algorithm> using namespace std; struct Dot { double x,y; }dot[105]; double caculateDistance(const Dot a,const Dot b) //两点间的距离 { return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)); } struct Node { int p,q; double dis; bool friend operator < (Node a,Node b) { return a.dis < b.dis; } }; vector<Node> data; int f[105]; //父节点 int find(int x) //查找 { if (x != f[x]) f[x] = find(f[x]); return f[x]; } bool join(int x,int y) //合并 { int fx = find(x); int fy = find(y); if (fx != fy) { f[fx] = fy; return true; } return false; } int main() { int n; scanf ("%d",&n); for (int i = 1 ; i <= n ; i++) f[i] = i; for (int i = 1 ; i <= n ; i++) scanf ("%lf%lf",&dot[i].x,&dot[i].y); for (int i = 1 ; i <= n ; i++) { for (int j = i+1 ; j <= n ; j++) { double dis = caculateDistance(dot[i],dot[j]); if (dis >= 10 && dis <= 1000) { Node t; t.p = i; t.q = j; t.dis = dis; data.push_back(t); } } } sort(data.begin(),data.end()); int ant = 0; //已经连上的边 double ans = 0; for (int i = 0 ; i < data.size() ; i++) { if (join(data[i].p,data[i].q)) { ans += data[i].dis; ant++; } if (ant == n-1) //剪枝 break; } if (ant == n-1) printf ("%lf\n",ans); else printf ("-1\n"); return 0; }