摘要:建最大生成树中考虑贡献

CF437D The Child and Zoo

题面

题目分析

题意相当于是一张点权图,对于任意一对点$(u,v)$,选择一条经过的点中$\min\{a_i\}$最大的路径,设这个值为$f(u,v)$,求:

如果是边权图的话反证法易证得点对间的这条路径一定在最大生成树中.

点权图做一个转化,将边权赋为连接的两个点中权值较小的那一个,因为选这条边就一定经过这两个点.

将边按边权单减排序,考虑kruskal算法的过程,我们加入一条新边时,经过这条边两边的连通块的路径均会以这条边作为最小值,所以可以直接统计贡献.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl big=100010;
lxl n,m,ConCnt;
double ans;
lxl val[big],fa[big],size[big];
struct _Edge
{
lxl u,v,w;
inline bool operator <(const _Edge &another)const
{
return w>another.w;
}
}e[big];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
lxl find(lxl x){return x==fa[x]?x:find(fa[x]);}
inline void merge(lxl x,lxl y)
{
if(size[y]>size[x])size[y]+=size[x],fa[x]=y;
else size[x]+=size[y],fa[y]=x;
}
int main(void)
{
n=read(),m=read();
for(R int i(1);i<=n;val[i]=read(),fa[i]=i,size[i]=1,++i);
for(R int i(1);i<=m;++i)
{
lxl u=read(),v=read(),w=std::min(val[u],val[v]);
e[i]=(_Edge){u,v,w};
}
std::sort(e+1,e+1+m);
for(R int i(1);i<=m;++i)
{
lxl x=e[i].u,y=e[i].v,w=e[i].w;
lxl FaX=find(x),FaY=find(y);
if(FaX!=FaY)
{
ans+=size[FaX]*size[FaY]*w;
merge(FaX,FaY);
if(++ConCnt==n-1)break;
}
}
printf("%lf\n",2*ans/(double)(n*(n-1)));
return 0;
}