这个题目让我想起了上次在湘潭赛的那道跪死了的题。也是最值问题，这个也是，有n个动物园 每个都有权值 然后被m条路径相连接，保证图是连通的，然后求所有的p[i][j]之和.i,j为任意两个zoo，pij就为i到j路上遇到的包括i j在内的最小权值的zoo
然后我就焦头烂额了一下，这个明显就是看某个最小值为最后的结果发挥了多少次作用，但这个是图，要知道某个节点到底给多少条路径贡献出了最小值，还真是有点没头绪（在已知的复杂度一看 最多只能用nlogn的），最后是看了解答才知道的
用并查集来解决某个最小值到底出现多少次，首先 其实不要被点弄得迷糊了，先落实到边权值来，每条边的权值就等于两个端点中那个小的，然后我们可以发现最大的边，仅仅只会对两个端点的那条路产生影响，然后次大的边，会对自己 以及他的邻边若是最大边，也会产生影响。
这就要用到并查集了，首先所用的点都是独立集，然后从最大的边开始，如果两个端点不在一个集合，便并在一起，并且这次边产生的影响次数 为 rank[r1]*rank[r2]，用乘法原理得出，因为是降序的，已经合并起来的点，全都是经历了更长的边，所以用乘法原理，当前两个端点所在集合的个数互乘一下，便是此刻的边产生的影响次数。
162716n1不思议迷宫、这样一下来，便可算出结果。
不得不是，并查集虽然写起来简单，真的是奥妙无穷。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 200000+10; struct node {int u,v,w;bool operator <(const node&rhs) const{return w>rhs.w;} }E[N]; int A[N]; int f[N],sum[N]; int cnt,n,m; void add(int a,int b) {E[cnt].u=a;E[cnt].v=b;E[cnt++].w=min(A[a],A[b]); } int findset(int x) {if (x!=f[x]) f[x]=findset(f[x]);return f[x]; } int main() {while (scanf("%d%d",&n,&m)!=EOF){cnt=0;for (int i=1;i<=n;i++){scanf("%d",&A[i]);f[i]=i;sum[i]=1;}int a,b;for (int i=1;i<=m;i++){scanf("%d%d",&a,&b);add(a,b);}sort(E,E+m);double ans=0;for (int i=0;i<m;i++){int r1=findset(E[i].u);int r2=findset(E[i].v);if (r2!=r1){ans+=(double)sum[r1]*sum[r2]*E[i].w*1.0;f[r1]=r2;sum[r2]+=sum[r1];}}ans*=2.0;ans/=(double)(n*1.0*(n-1));printf("%.6lf\n",ans);}return 0; }
