当前位置：首页 > news >正文

数据结构选讲（更新中）

news 来源：原创 2025/5/15 12:05:00

参考 smWCDay7 数据结构选讲2 by yyc 。

可能会补充的：

AT_cf17_final_j TreeMST 的 F2 Boruvka算法

AT_cf17_final_j Tree MST

link
题意
给定一棵 $n$ 个点的树，点有点权 $w_i$ ，边有边权。建立一张完全图 $G$ ，节点 $u, v$ 之间的边长为 $w_u + w_v + dis(u, v)$ 。求 $G$ 的 $MST$ （最小生成树）的边权和。

$\le 2 \times 10^5 ，1 \le w_i \le 10^9$

思路
前置指示：点分治

引理：边 $e$ 在边集 $E$ 的最小生成树中，则对于任意 $E_0 ⊆ E$ ，e 也在边集 $E_0$ 的最小生成树中。
证明：考虑 kruskal。
推论：将边分为若干组，分别求最小生成树，再合并求最小生成树，结果正确。

题目是说建立一张完全图然后求其的 $MST$ ,但是这样的边是 $n^2$ 级别的，考虑去掉一些多余的边，只保留有用的边。所以可以将完全图 $G$ 分成很多个边集，分别求 $MST$ （不必强制联统），然后保留有用边，最后再综合求 $MST$ 就是答案了。
考虑 点分治，以重心为根，将树分成几个子树，那么就只用处理跨越重心的边即可。
记 $dis_i$ 表示点 $i$ 到重心的距离，跨越重心的边 $(u, v)$ ，边权是 $w_u + dis_u + w_v + dis_v$ 。由于每个点 $i$ 都要贡献至少一次 $w_i+dis_i$ ，另外一边肯定选最小的 $w_j+dis_j$ ，所以我们只需要选择 $w_i + dis_i$ 最小的点，让它和所有其他点连边，该菊花图就是最小生成树。（在同一棵子树内连了边也不影响结果，因为它们的边权比真实值要大 $dis_u + dis_v \gt dis_{u,v}$ ）。这样边的数量就减到了 $n l o g n$ ，总时间复杂度为 $O(nlog^2n)$ 。

好像还有一种方法，要用到 Boruvka算法 ，后续可能会学……

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+5;int idx,head[maxn];
struct EDGE{ int v,next; ll w; }e[maxn*2];
void Insert(int u,int v,ll w){e[++idx]={v,head[u],w};head[u]=idx;
}int siz[maxn],mxson[maxn],pot[maxn],tn;
bool vis[maxn];
void Dfs(int x,int fa){pot[++tn]=x,siz[x]=1,mxson[x]=0;for(int i=head[x];i;i=e[i].next){int v=e[i].v;if(!vis[v]&&v!=fa){Dfs(v,x);siz[x]+=siz[v];mxson[x]=max(mxson[x],siz[v]);}}
}int Get_root(int x){tn=0,Dfs(x,0);int root=0;for(int i=1;i<=tn;i++){mxson[pot[i]]=max(mxson[pot[i]],tn-siz[pot[i]]);if(!root||mxson[root]>mxson[pot[i]]) root=pot[i]; }return root;
}int id;
ll a[maxn],dis[maxn];
void Dfs2(int x,int fa){for(int i=head[x];i;i=e[i].next){int v=e[i].v;if(!vis[v]&&v!=fa){dis[v]=dis[x]+e[i].w;Dfs2(v,x);}}if(!id||a[x]+dis[x]<a[id]+dis[id]) id=x;
}int cnt;
struct EDGE2{ int u,v; ll w; }te[maxn*20];
void Solve(int rt){dis[rt]=0,id=0,Dfs2(rt,0);for(int i=1;i<=tn;i++)te[++cnt]={id,pot[i],a[id]+dis[id]+a[pot[i]]+dis[pot[i]]};vis[rt]=1;for(int i=head[rt];i;i=e[i].next){int v=e[i].v;if(!vis[v]) Solve(Get_root(v));}
}int fa[maxn];
int Find_fa(int x){ return fa[x]==x?x:fa[x]=Find_fa(fa[x]); }int main(){int n; cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<n;i++){int x,y,z; cin>>x>>y>>z;Insert(x,y,z),Insert(y,x,z);}Solve(Get_root(1));sort(te+1,te+cnt+1,[](EDGE2 a,EDGE2 b){ return a.w<b.w; });for(int i=1;i<=n;i++)fa[i]=i;ll ans=0;for(int i=1;i<=cnt;i++){int fx=Find_fa(te[i].u),fy=Find_fa(te[i].v);if(fx!=fy) fa[fy]=fx,ans+=te[i].w;}cout<<ans;return 0;
}

目录

AT_cf17_final_j Tree MST

相关文章：