【Vijos-P1579】宿命的PSS-逆向Kruskal

    xiaoxiao2024-05-16  1

    测试地址

    题目大意:给定一棵最小生成树,求以它为唯一的最小生成树的完全图(每两点之间都直接有边相连的图)的最小边权之和。

    做法:首先把最小生成树中的边按边权从小到大排序,依次枚举每条边,根据Kruskal的求最小生成树思路可知,加入这条边前两点属于不同的集合,而这条边又一定是连接这两个集合的边中边权最小的(因为这是唯一的最小生成树),于是要构成满足条件的最小完全图,需要在两个集合之间连上(第一个顶点所在集合的点数*第二个顶点所在集合的点数-1)条边权为(当前边边权+1)的边,并把这些边权加入到答案中。然后只需要在并查集的合并操作中顺便维护集合内的点数即可。

    以下是本人代码:

    #include <cstdio> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; long n,a[20010]={0},b[20010]={0},c[20010]={0}; long f[20010]={0}; long long num[20010]={0},ans; long find(long x) { long r=x,i=x,j; while(f[r]!=r) r=f[r]; while(i!=r) {j=f[i];f[i]=r;i=j;} return r; } void merge(long a,long b) { long fa=find(a),fb=find(b); f[fa]=fb; num[fb]+=num[fa]; } void quicksort(long l,long r) { if (l>=r) return; long mid=c[(l+r)/2]; long i=l,j=r; while(i<=j) { while(c[i]<mid) i++; while(c[j]>mid) j--; if (i<=j) { long temp; temp=c[i];c[i]=c[j];c[j]=temp; temp=a[i];a[i]=a[j];a[j]=temp; temp=b[i];b[i]=b[j];b[j]=temp; i++;j--; } } quicksort(l,j); quicksort(i,r); } void input() { scanf("%ld",&n); for(int i=1;i<=n-1;i++) { scanf("%ld %ld %ld",&a[i],&b[i],&c[i]); ans+=c[i]; } for(int i=1;i<=n;i++) { f[i]=i; num[i]=1; } } void work() { for(int i=1;i<=n-1;i++) { long fa=find(a[i]),fb=find(b[i]); ans+=(num[fa]*num[fb]-1)*(c[i]+1); merge(a[i],b[i]); } } void output() { printf("%I64d",ans); } int main() { input(); quicksort(1,n-1); work(); output(); return 0; }

    转载请注明原文地址: https://ju.6miu.com/read-1288611.html
    最新回复(0)