Codeforces 437D 贪心+并查集

时间:2022-12-22 08:48:42

这个题目让我想起了上次在湘潭赛的那道跪死了的题。也是最值问题,这个也是,有n个动物园 每个都有权值 然后被m条路径相连接,保证图是连通的,然后求所有的p[i][j]之和.i,j为任意两个zoo,pij就为i到j路上遇到的包括i j在内的最小权值的zoo

然后我就焦头烂额了一下,这个明显就是看某个最小值为最后的结果发挥了多少次作用,但这个是图,要知道某个节点到底给多少条路径贡献出了最小值,还真是有点没头绪(在已知的复杂度一看 最多只能用nlogn的),最后是看了解答才知道的

用并查集来解决某个最小值到底出现多少次,首先 其实不要被点弄得迷糊了,先落实到边权值来,每条边的权值就等于两个端点中那个小的,然后我们可以发现最大的边,仅仅只会对两个端点的那条路产生影响,然后次大的边,会对自己 以及他的邻边若是最大边,也会产生影响。

这就要用到并查集了,首先所用的点都是独立集,然后从最大的边开始,如果两个端点不在一个集合,便并在一起,并且这次边产生的影响次数 为 rank[r1]*rank[r2],用乘法原理得出,因为是降序的,已经合并起来的点,全都是经历了更长的边,所以用乘法原理,当前两个端点所在集合的个数互乘一下,便是此刻的边产生的影响次数。

这样一下来,便可算出结果。

不得不是,并查集虽然写起来简单,真的是奥妙无穷。

#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;
}