Uva 10034 进来复习一下最小生成树模板

一、题意

输入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;
    }
    .....
}

终于到图论部分了....