欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LibreOJ #10067 构造完全图(由最小生成树构造最小完全图)

程序员文章站 2022-06-16 08:58:24
...

题目链接https://loj.ac/problem/10067
LibreOJ #10067 构造完全图(由最小生成树构造最小完全图)
完全图
若一个图的每一对不同顶点恰有一条边相连,则称为完全图。
完全图是每对顶点之间都恰连有一条边的简单图。n个端点的完全图有n个端点及n(n − 1) / 2条边。由
最小生成树复原最小完全图
最小生成树T,T中的每一条边都是一条割边
去掉任意一条树T中的边,这个树一定会变成两个联通块,令其为A、B。
要将T扩展为完全图G,那么显然 A中的每个点都需要与B中的所有点相连
A中新发出的连边的权值一定是大于(若等于则存在多种最小生成树解,不合题意)出发点在树上的相接边的权值的。
再一看数据量,单独枚举肯定不行。由联通块可以联想到并查集,发现可行。
对于一条最小生成树上的边E<A,B>,可以看做E连接了A,B两个联通块。
那么要将A、B两块连接为一个完全图需要加的边数就是 cnt[A] * cnt[B]-1,其中cnt表示联通块中的结点个数
边的权值一定是大于E的权值的,要使其最小,那么这些边的权值都是 E的权值+1
那么合并A、B两个联通块的花费就是 (边E.权+1)*(cnt[A]*cnt[B]-1)。ans在每次合并联通块时加上花费即可求解。
另外一点,因为要求的是最小的完全图,所以有一个贪心策略:先把树上的边按照权值从小到大排序,然后枚举即可。
代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
typedef long long LL;
struct node
{
    int u,v;
    LL w;
} val[N];
int n,f[N],ans[N];
int getf(int x)
{
    if(x!=f[x])
        f[x]=getf(f[x]);
    return f[x];
}
int cmp(node t1,node t2)
{
    return t1.w<t2.w;
}
int main()
{
    scanf("%d",&n);
    LL sum=0;
    for(int i=1; i<n; i++)
    {
        scanf("%d%d%lld",&val[i].u,&val[i].v,&val[i].w);
        sum+=val[i].w;
    }
    for(int i=1;i<=n;i++)
    {
        f[i]=i;
        ans[i]=1;
    }
    sort(val+1,val+n,cmp);
    for(int i=1; i<n; i++)
    {
        int t1=getf(val[i].u);
        int t2=getf(val[i].v);
        sum+=(LL)(val[i].w+1)*(ans[t1]*ans[t2]-1);
        f[t1]=t2;
        ans[t2]+=ans[t1];
    }
    printf("%lld\n",sum);
    return 0;
}
相关标签: 最小生成树