首页 > 代码库 > Codeforces 437D 贪心+并查集

Codeforces 437D 贪心+并查集

2024-07-10 21:16:35   221人阅读

这个题目让我想起了上次在湘潭赛的那道跪死了的题。也是最值问题，这个也是，有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;}

 


联系
我们