[南海云课堂] [kruskal] [贪心] 走廊泼水节

_Cheems · 2023-08-18 19:13:24 · 个人记录

题意

给定一棵 N 个节点的树，要求增加若干条边，把这棵树扩充为完全图，并满足图的唯一最小生成树仍然是这棵树。

求增加的边的权值总和最小是多少。

注意： 树中的所有边权均为整数，且新加的所有边权也必须为整数。

思路

主要考察了对 \rm{kruskal} 算法底层原理的理解运用。

不妨思考怎么加边才能使原最小生成树唯一。

回顾 \rm{kruskal} 的过程：从小到大取 n-1 条较小边，并使得每次得到的边的两个端点属于不同连通块。

那么最简单的加边方式就是在同一个连通块内连边，为了保证加边后还是原来的最小生成树，还需使得这些边的边权大于最近一次合并这个连通块的边的边权。

回到 \rm{kruskal}，我们每次取的边是 e(u,v)，令其权值为 w。由于先前的循环已经使得 u,v 所在连通块 U,V 都为完全图，那么实际上就是连接了 U,V 这两个完全图并将其合并为 P，我们只需计算新加的边是多少即可。

那么新加的边数 tot=siz(P)-siz(U)-siz(V)-1，注意 e(u,v) 不能被算入。于是使 P 变为完全图的最小花费就是 tot*(w+1)，注意要使得原生成树唯一所以边权不能等于 w。

至于 siz 数组，在并查集合并、查询的过程中维护即可。

代码

好累啊，其实放代码里就两句话的事。

#include<bits/stdc++.h>
using namespace std;
const int N=6e3+5;
int t,n,u,v,w,ans;
int fa[N],siz[N];
struct edge{
    int u,v,w;
}e[2*N];
inline int find(int k){
    if(fa[k]==k){
        return k;
    }
    return fa[k]=find(fa[k]);
}
inline int get(int k){
    return k*(k-1)/2;
}
int main(){
    cin>>t;
    while(t--){
        ans=0;
        scanf("%d",&n);
        for(int i=1; i<=n;i++){
            fa[i]=i;
            siz[i]=1;
        }
        for(int i=1; i<=n-1;i++){
            scanf("%d%d%d",&u,&v,&w);
            e[i]={u,v,w};
        }
        sort(e+1,e+n,[](edge a,edge b){return a.w<b.w;});
        for(int i=1; i<=n-1;i++){
            int u=e[i].u,v=e[i].v,w=e[i].w;
            int fu=find(u),fv=find(v);
            ans+=(get(siz[fu]+siz[fv])-get(siz[fu])-get(siz[fv])-1)*(w+1); //计算答案 
            fa[fu]=fv;
            siz[fv]+=siz[fu]; //维护 siz 
        }
        printf("%d\n",ans);
    }
    return 0;
}