LibreOJ10067. 「一本通 3.1 练习 2」构造完全图【Kruskal】

10067. 「一本通 3.1 练习 2」构造完全图

【题目描述】

传送门

【题解】

我们模拟Kruskal的过程,然后两个联通块相连代价为w,说明联通块其他每条边的代价>w。

代码如下

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
int n,fa[100005];LL Ans,Siz[100005];
struct xcw{
    int x,y,w;
    bool operator <(const xcw b)const{return w<b.w;}
}a[100005];
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret<<1)+(ret<<3)+ch-48;
    return f?ret:-ret;
}
int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}
int merge(int x,int y){fa[y]=x,Siz[x]+=Siz[y];}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    n=read();
    for(int i=1;i<n;i++) a[i]=(xcw){read(),read(),read()};
    for(int i=1;i<=n;i++) fa[i]=i,Siz[i]=1;
    sort(a+1,a+n);
    for(int i=1;i<n;i++){
        int fx=get(a[i].x),fy=get(a[i].y),w=a[i].w;
        Ans+=(Siz[fx]*Siz[fy]-1)*(w+1)+w;
        merge(fx,fy);
    }
    printf("%lld\n",Ans);
    return 0;
}

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部