一、题意
输入n表示有n个点,然后输入每个点的实数坐标(xi, yi),求连通所有点的最小长度和。
二、解析
这是一道裸的最小生成树问题,边权就是两点间的距离。直接上Kruskal算法模板。
总是得来一道模板题复习复习的。
三、代码
#include <iostream> #include <algorithm> #include <vector> #include <cmath> #include <iomanip> using namespace std; const int maxn = 100 + 5; struct edge { int u, v; double len; edge(int u, int v, double len) : u(u), v(v), len(len) {} bool operator < (const edge& rhs) const { return len < rhs.len; } }; int kase, n, Fa[maxn]; double x[maxn], y[maxn]; vector<edge> E; double dist(int i, int j) { return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])); } int find(int x) { return Fa[x] == x ? x : Fa[x] = find(Fa[x]); } int main() { cin >> kase; while(kase --) { cin >> n; E.clear(); for(int i = 0; i < n; i ++) cin >> x[i] >> y[i]; for(int i = 0; i < n; i ++) for(int j = i + 1; j < n; j ++) E.push_back(edge(i, j, dist(i, j))); for(int i = 0; i < n; i ++) Fa[i] = i; sort(E.begin(), E.end()); double ans = 0; for(const auto& e : E) { int u = find(e.u), v = find(e.v); if(u == v) continue; Fa[u] = v; ans += e.len; } cout << fixed << setprecision(2) << ans << endl; if(kase) cout << endl; } }
四、归纳
- Kruskal算法求最小生成树模板:
struct edge { // 边结构定义 int u, v, w; edge(int u, int v, double len) : u(u), v(v), w(w) {} bool operator < (const edge& rhs) const { //按边权从小到大排列 return len < rhs.len; } }; int n, Fa[maxn]; // 并查集要使用的Fa数组 vector<edge> E; int find(int x) { return Fa[x] == x ? x : Fa[x] = find(Fa[x]); // 路径压缩 } int main() { ...... for(int i = 0; i < n; i ++) Fa[i] = i; // Fa初始化 sort(E.begin(), E.end()); // 按结点从小到大排序 int ans = 0; for(const auto& e : E) { int u = find(e.u), v = find(e.v); if(u == v) continue; Fa[u] = v; // 若不连通则将其连通 ans += e.len; } ..... }
终于到图论部分了....