B. The Child and Zoo
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://codeforces.com/contest/438/problem/B
Description
Of course our child likes walking in a zoo. The zoo has n areas, that are numbered from 1 to n. The i-th area contains ai animals in it. Also there are m roads in the zoo, and each road connects two distinct areas. Naturally the zoo is connected, so you can reach any area of the zoo from any other area using the roads.
Our child is very smart. Imagine the child want to go from area p to area q. Firstly he considers all the simple routes from p to q. For each route the child writes down the number, that is equal to the minimum number of animals among the route areas. Let's denote the largest of the written numbers as f(p, q). Finally, the child chooses one of the routes for which he writes down the value f(p, q).
After the child has visited the zoo, he thinks about the question: what is the average value of f(p, q) for all pairs p, q (p ≠ q)? Can you answer his question?
Input
The first line contains two integers n and m (2 ≤ n ≤ 105; 0 ≤ m ≤ 105). The second line contains n integers: a1, a2, ..., an (0 ≤ ai ≤ 105). Then follow m lines, each line contains two integers xi and yi (1 ≤ xi, yi ≤ n; xi ≠ yi), denoting the road between areas xi and yi.
All roads are bidirectional, each pair of areas is connected by at most one road.
Output
Output a real number — the value of 
.
The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 4.
Sample Input
4 310 20 30 401 32 34 3
Sample Output
16.666667
HINT
题意
给你一个图
然后f(p,q)表示从p到q的所有路径中，最小价值是多少
然后让你求sigma(p,q,p!=q)f(p,q) /n*(n-1)
题解：
并查集
从大往小考虑，然后加进这个图里面，在不断加点的过程中，新加入的点一定是最小的点，于是新产生的路径，这些路径的权值，就是这个点的权值
所以并查集跑一发就好啦，维护并查集的时候，顺便维护一下每个集合的个数就好了
代码
#include#include #include using namespace std;#define maxn 100005int fa[maxn],a[maxn],num[maxn];int fi(int x){ return fa[x]==x?x:fa[x]=fi(fa[x]);}struct node{ int x,y,v;}d[maxn];bool cmp(node a,node b){ return a.v>b.v;}int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); fa[i]=i;num[i]=1; } for(int i=1;i<=m;i++) { scanf("%d%d",&d[i].x,&d[i].y); d[i].v = min(a[d[i].x],a[d[i].y]); } sort(d+1,d+1+m,cmp); double ans = 0; for(int i=1;i<=m;i++) { int xx = fi(d[i].x); int yy = fi(d[i].y); if(xx!=yy) { ans += 1.0 * num[xx] * num[yy] * d[i].v; fa[xx]=yy; num[yy]+=num[xx]; } } printf("%.12lf\n",ans*2/n/(n-1));}