本题就是给定一个图，有些点已经有边了， 在有边的情况下求出最小生成树。
如果用kruskal算法，已经存在的边实际上是在为我们初始化并查集，我们要把这些边的左右端点的集合并起来就行了。
在完成了并查集的初始化，就可以套模板求最小生成树了。代码如下：
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <queue> #include <map> using namespace std; typedef long long int LL; const int maxn = 1005; const int INF = 0x3f3f3f3f; int p[maxn], n, m; struct Node{ int x, y; }; Node a[maxn]; struct edge{ int u, v; double dis; edge(int a, int b, double c){u = a; v = b; dis = c;} edge(); bool operator < (const edge &b) const{ return dis < b.dis; } }; vector<edge> edges; int find_root(int x){//并查集找根节点 if (p[x] == x) return x; return p[x] = find_root(p[x]); } double kruskal(){//模板 sort(edges.begin(), edges.end()); double res = 0; for (int i = 0; i < edges.size(); i++){ edge e = edges[i]; int x = e.u, y = e.v; double cost = e.dis; int rx = find_root(x); int ry = find_root(y); if (rx != ry){ p[rx] = ry; res += cost; } } return res; } int main() { //freopen("1.txt", "r", stdin); scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++){ scanf("%d%d", &a[i].x, &a[i].y); for (int j = 1; j <= i - 1; j++){//因为没写double的类型转换wa了无数次 double cost = sqrt((double)(a[i].x - a[j].x) * (a[i].x - a[j].x) + (double)(a[i].y - a[j].y) * (a[i].y - a[j].y)); edges.push_back(edge(j, i, cost)); } } for (int i = 1; i <= n; i++) p[i] = i; for (int i = 1; i <= m; i++){//已经存在的边相当于在为我们初始化并查集 int x, y; scanf("%d%d", &x, &y); int rx = find_root(x); int ry = find_root(y); if (rx != ry) p[rx] = ry; } printf("%.2f\n", kruskal()); return 0; } 除了kruskal，我们也可以使用prim算法。在prim算法中，我们把已经存在的边的权值设为0。这样一来，在运行prim算法的时候。假设一条已知边为u，v。在把u加入了已知集合之后，用u更新周围点的mincost，因为u到v的权值是0，所以v到已知集合的最短距离就会更新成0。也就是u，v这条边肯定会被选进去，并且选择的代价是0。完全符合题目的意思！
代码如下：
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <queue> #include <map> using namespace std; typedef long long int LL; const int maxn = 1005; const int INF = 0x3f3f3f3f; int n, m; struct Node{int x, y;}; Node a[maxn]; double G[maxn][maxn], mincost[maxn]; int vis[maxn]; double prim(){ for (int i = 1; i <= n; i++){ mincost[i] = INF; vis[i] = 0; } mincost[1] = 0; double res = 0; while (1){ int v; double m = INF; for (int i = 1; i <= n; i++) if (!vis[i] && m > mincost[i]) m = mincost[v = i]; if (m == INF) break; res += m; vis[v] = 1; for (int i = 1; i <= n; i++)//因为任意两个点之间肯定有边，就省去判断是否有边的步骤了 if (mincost[i] > G[v][i]) mincost[i] = G[v][i]; } return res; } int main() { //freopen("1.txt", "r", stdin); scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++){ scanf("%d%d", &a[i].x, &a[i].y); for (int j = 1; j <= i - 1; j++){ double cost = sqrt((double)(a[i].x - a[j].x) * (a[i].x - a[j].x) + (double)(a[i].y - a[j].y) * (a[i].y - a[j].y)); G[i][j] = G[j][i] = cost; } } for (int i = 1; i <= m; i++){ int x, y; scanf("%d%d", &x, &y); G[x][y] = G[y][x] = 0; } printf("%.2f\n", prim()); return 0; }
