清北学堂NOIP训练营内部试题！

解析在代码后面

代码

#include

#include

#define N 20001

#define M 100001

using namespace std;

typedef long long LL;

int fa[N],siz[N];

struct node

{

    int u,v,w;

}e[M];

bool cmp(node p,node q)

{

    return p.w<>

}

int find(int i) { return fa[i]==i ? i : fa[i]=find(fa[i]); }

int main()

{

    freopen('detective.in','r',stdin);

    freopen('detective.out','w',stdout);

    int n,m;

    scanf('%d%d',&n,&m);

    for(int i=1;i<=m;i++)>

    sort(e+1,e+m+1,cmp);

    for(int i=1;i<=n;i++) fa[i]="">

    int u,v;

    LL sum=0,cnt=0;

    for(int i=1;i<>

    {

        u=find(e[i].u); v=find(e[i].v);

        if(u==v) continue;

        sum+=e[i].w;

        cnt+=1ll*siz[u]*siz[v]*e[i].w;

        fa[v]=u; siz[u]+=siz[v];

    }

    printf('%.2lf',sum-cnt*2.0/(n*(n-1)));

}

解析：

60分做法：

先做一遍最小生成树

枚举两个点i，j，那么替换掉的是最小生成树上i，j路径上权值最大的边

倍增维护

时间复杂度：O（n*n*logn）

 

100分做法：

换一个角度，考虑被替换掉的边的贡献

边e要想被替换掉，那么点 i，j 要满足两个条件：

① 设e的两端点为u，v，i∈u，j∈v

② e的边权是连通 i，j 必经之路（最短路）上边权最大的边

怎么找这条边？——Kruscal算法

Kruscal算法每次找还没有加进去的权值最小的边，所以满足必经之路

还没有加进去的边权最小的边，是已加进去的边权最大的边，所以满足路径上边权最大

所以，设最小生成树的总权值为sum，设当前边权为w，当前边连接的两点的集合大小分别为 s1、s2

ans=（sum*n*（n-1）- 2*Σ s1*s2*w）/（n*(n-1)）

n*（n-1）：任意选两个点共有这些选法

Σ 前乘2：u，v 和 v，u 算不同的方案