CF437D The Child and Zoo

CF437D The Child and Zoo

首先你需要语文水平。

就是找到 (u ightarrow v) 所有简单路径上的最小值的最大值。即最大生成树。。。

容易发现，经过一条边必然经过其两端的点，所以我们可以设边权为 (val_{u,v} = min(a_u, a_v))

然后走最大生成树，合并并查集的时候计算，最后除一下。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

typedef int ll;
const ll MAXN = 1e6+10;

struct edge {
    ll x, y, v;
    friend bool operator < (edge a, edge b) {return a.v > b.v;}
} E[MAXN];

ll N, M, val[MAXN], fa[MAXN], siz[MAXN];
double ans;

ll find_(ll);

int main() {
    scanf("%d%d", &N, &M);
    for (ll i = 1; i <= N; i++)
        scanf("%d", val+i), fa[i] = i, siz[i] = 1;
    for (ll i = 1; i <= M; i++) {
        scanf("%d%d", &E[i].x, &E[i].y);
        E[i].v = min(val[E[i].x], val[E[i].y]);
    }
    sort(E+1, E+M+1);
    for (ll i = 1, cnt = 1; cnt < N && i <= M; i++) {
        ll fx = find_(E[i].x), fy = find_(E[i].y);
        if (fx != fy) {
            fa[fx] = fy;
            ans += 1.0 * siz[fx] * siz[fy] * E[i].v;
            siz[fy] += siz[fx];
        }
    }
    long long sum = (N * (N - 1)) / 2;
    printf("%.6f
", ans / sum);
    return 0;
}

ll find_(ll x) {return fa[x] == x ? x : fa[x] = find_(fa[x]);}