给你一张无向图,每个点有一个权值,对于一条从l到r 的边权值是l到r路径上最小的点的权值,(多条路取最大的权值),然后求每两个点之间的权值和/点对数
题解:并查集维护,先从点大的边排序,然后依次加边,这样每次加进来的保证是当前最大 的,然后每次合并都要加上两端的最小值*两端的size,类似与每一个最小值算贡献
#pragma comment(linker, "/stack:200000000") #pragma GCC optimize("Ofast,no-stack-protector") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-12; const int N=100000+10,maxn=400000+10,inf=0x3f3f3f3f; ll a[N],father[N],sz[N]; struct edge{ ll from,to,c; }e[N]; bool cmp(edge x,edge y) { return x.c > y.c; } ll Find(ll x) { return x==father[x]?x:father[x]=Find(father[x]); } int main() { ll n,m; scanf("%lld%lld",&n,&m); for(ll i=1;i<=n;i++) { scanf("%lld",&a[i]); father[i]=i; sz[i]=1; } for(int i=0;i<m;i++) { scanf("%lld%lld",&e[i].from,&e[i].to); e[i].c = min(a[e[i].from], a[e[i].to]); } sort(e,e+m,cmp); ll ans=0; for(int i=0;i<m;i++) { ll x=e[i].from,y=e[i].to; // cout<<x<<" "<<y<<" "<<sz[x]<<" "<<sz[y]<<endl; ll fx=Find(x),fy=Find(y); if(fx!=fy) { ans+=min(a[x],a[y])*sz[fx]*sz[fy]; father[fx]=fy; sz[fy]+=sz[fx]; } } ll te=(n-1)*n/2; printf("%.12f ",(double)ans/te); return 0; } /******************** ********************/