首页 > 代码库 > uva10034

uva10034

题目链接请戳 这里

 

解题思路

克鲁斯卡尔求最小生成树

 

代码

#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
using namespace std;

const int N = 110;

struct point {
    double x, y;
}V[N];
//边集
struct edge {
    double w;
    int u, v;
}e[N*N];

int d[N*N];    //存储每条边的编号,用来间接排序
int set[N];    //并查集
int n;

double get_lenth(point a, point b)
{
    double lenth;
    lenth = sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
    return lenth;
}
int cmp(const int i, const int j)
{
    return e[i].w < e[j].w;
}
void make_set()
{
    for (int i = 1; i <= n; i++) {
        set[i] = i;
    }
}
int find(int x)
{
    return set[x] == x ? x : set[x] = find(set[x]);
}
double Kru(int m)
{
    double ans = 0;
    for (int i = 0; i < m; i++) {
        int t = d[i];
        int fa = find(e[t].u);
        int fb = find(e[t].v);
        if (fa != fb) {
            set[fa] = fb;
            ans += e[t].w;
        }
    }
    return ans;
}
int main()
{
    int tests;
    cin >> tests;
    while (tests--) {
        int size = 0;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> V[i].x >> V[i].y;
        }
        //建图,每对顶点之间都有一条边
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) if (i != j) {
                int x = size;
                e[x].w = get_lenth(V[i], V[j]);
                e[x].u = i; e[x].v = j;
                d[x] = x;
                size++;
            }
        }
        //初始化并查集
        make_set();
        //对边集排序
        sort(d, d + size, cmp);
        //输出结果,保留小数点后两位数字
        cout.flags(ios::fixed);
        cout << setprecision(2) << Kru(size) << endl;
        if (tests) cout << endl;
    }
}

 

uva10034