kuangbin 专题八 生成树

#include <cstdio>
#include <algorithm>
#define N 101
using namespace std;
int t, n, m, p[N];
struct edge
{
    int w, u, v;
    bool operator<(const edge &a) const { return w < a.w; }
} e[N * N];
int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}
void kruskal()
{
    int sum = 0, res = 0;
    for (int i = 1; i <= n; ++i)
        p[i] = i;
    sort(e, e + m);
    for (int i = 0; i < m; ++i)
    {
        int r = i;
        while (r < m && e[i].w == e[r].w)
            ++r;
        --r;
        for (int j = i; j <= r; ++j)
        {
            int a = find(e[j].u), b = find(e[j].v);

            if (a != b)
                sum += e[j].w;
        }
        for (int j = i; j <= r; ++j)
        {
            int a = find(e[j].u), b = find(e[j].v);
            if (a != b)
                p[a] = b, res += e[j].w;
        }
        i = r;
    }
    if (sum != res)
        printf("Not Unique!\n");
    else
        printf("%d\n", res);
}
int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < m; ++i)
            scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
        kruskal();
    }
    return 0;
}

#include<bits/stdc++.h>
#define N 1001
#define M 2002
using namespace std;
int T, n, x[N], y[N], p[N];
bool st[N];
double g[N][N], d[N], w[M];
int h[N], e[M], ne[M], tot;
int path[N];
vector<pair<int, int>> vp;
void add(int u, int v, int ww)
{
    e[tot] = v, w[tot] = ww, ne[tot] = h[u], h[u] = tot++;
}
double prim()
{
    double res = 0;
    for (int i = 0; i < n; ++i)
        d[i] = 0x3f3f3f3f, st[i] = 0;
    d[0] = 0;
    for (int i = 0; i < n; ++i)
    {
        int t = -1;
        for (int j = 0; j < n; ++j)
            if (!st[j] && (t == -1 || d[j] < d[t]))
                t = j;
        st[t] = 1;
        if (i)
        {
            res += d[t];
            add(path[t], t, g[path[t]][t]);
            add(t, path[t], g[path[t]][t]);
            vp.push_back({t, path[t]});
        }
        for (int j = 0; j < n; ++j)
            if (!st[j] && d[j] > g[t][j])
                d[j] = g[t][j], path[j] = t;
    }
    return res;
}
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        memset(h, -1, sizeof h);
        tot = 0;
        vp.clear();
        for (int i = 0; i < n; ++i)
            scanf("%d%d%d", x + i, y + i, p + i);
        for (int i = 0; i < n; ++i)
        {
            g[i][i] = 0;
            for (int j = i + 1; j < n; ++j)
                g[i][j] = g[j][i] = sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));
        }
        double mst = prim(), ans = 0;
        for (auto &[u, v] : vp)
        {
            int p1 = 0, p2 = 0;
            function<void(int, int, int&)> dfs = [&](int f, int u, int& pv)
            {
                pv = max(pv, p[u]);
                for (int i = h[u]; ~i; i = ne[i])
                    if (e[i] != f)
                        dfs(u, e[i], pv);
            };
            dfs(u, v, p1), dfs(v, u, p2);
            ans = max(ans, (p1 + p2) / (mst - g[u][v]));
        }
        printf("%.2lf\n", ans);
    }
    return 0;
}