查网站二级域名,南化建设公司官网,汕头搜索引擎优化服务,办公室装修设计简约参考 smWCDay7 数据结构选讲2 by yyc 。
可能会补充的#xff1a; AT_cf17_final_j TreeMST 的 F2 Boruvka算法 目录 AT_cf17_final_j Tree MST AT_cf17_final_j Tree MST
link 题意 给定一棵 n n n 个点的树#xff0c;点有点权 w i w_i wi#xff0c;边有边权。建立…参考 smWCDay7 数据结构选讲2 by yyc 。
可能会补充的 AT_cf17_final_j TreeMST 的 F2 Boruvka算法 目录 AT_cf17_final_j Tree MST AT_cf17_final_j Tree MST
link 题意 给定一棵 n n n 个点的树点有点权 w i w_i wi边有边权。建立一张完全图 G G G节点 u , v u, v u,v 之间的边长为 w u w v d i s ( u , v ) w_u w_v dis(u, v) wuwvdis(u,v) 。求 G G G 的 M S T MST MST 最小生成树的边权和。 n ≤ 2 × 1 0 5 1 ≤ w i ≤ 1 0 9 n \le 2 \times 10^5 1 \le w_i \le 10^9 n≤2×1051≤wi≤109
思路 前置指示点分治 引理边 e e e 在边集 E E E 的最小生成树中则对于任意 E 0 ⊆ E E_0 ⊆ E E0⊆Ee 也在边集 E 0 E_0 E0 的最小生成树中。 证明考虑 kruskal。 推论将边分为若干组分别求最小生成树再合并求最小生成树结果正确。 题目是说建立一张完全图然后求其的 M S T MST MST ,但是这样的边是 n 2 n^2 n2 级别的考虑去掉一些多余的边只保留有用的边。所以可以将完全图 G G G 分成很多个边集分别求 M S T MST MST 不必强制联通然后保留有用边最后再综合求 M S T MST MST 就是答案了。 考虑 点分治以重心为根将树分成几个子树那么就只用处理跨越重心的边即可。 记 d i s i dis_i disi 表示 点 i i i 到重心的距离跨越重心的边 ( u , v ) (u,v) (u,v)边权是 w u d i s u w v d i s v w_u dis_u w_v dis_v wudisuwvdisv 。由于每个点 i i i 都要贡献至少一次 w i d i s i w_idis_i widisi另外一边肯定选最小的 w j d i s j w_jdis_j wjdisj 所以我们只需要选择 w i d i s i w_i dis_i widisi 最小的点让它和所有其他点连边该菊花图就是最小生成树。在同一棵子树内连了边也不影响结果因为它们的边权比真实值要大 d i s u d i s v d i s u , v dis_u dis_v \gt dis_{u,v} disudisvdisu,v 。这样边的数量就减到了 n l o g n nlogn nlogn总时间复杂度为 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n) 。
好像还有一种方法要用到 Boruvka算法 后续可能会学……
代码
#includebits/stdc.h
#define ll long long
using namespace std;
const int maxn2e55;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 ihead[x];i;ie[i].next){int ve[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){tn0,Dfs(x,0);int root0;for(int i1;itn;i){mxson[pot[i]]max(mxson[pot[i]],tn-siz[pot[i]]);if(!root||mxson[root]mxson[pot[i]]) rootpot[i]; }return root;
}int id;
ll a[maxn],dis[maxn];
void Dfs2(int x,int fa){for(int ihead[x];i;ie[i].next){int ve[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]) idx;
}int cnt;
struct EDGE2{ int u,v; ll w; }te[maxn*20];
void Solve(int rt){dis[rt]0,id0,Dfs2(rt,0);for(int i1;itn;i)te[cnt]{id,pot[i],a[id]dis[id]a[pot[i]]dis[pot[i]]};vis[rt]1;for(int ihead[rt];i;ie[i].next){int ve[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; cinn;for(int i1;in;i)cina[i];for(int i1;in;i){int x,y,z; cinxyz;Insert(x,y,z),Insert(y,x,z);}Solve(Get_root(1));sort(te1,tecnt1,[](EDGE2 a,EDGE2 b){ return a.wb.w; });for(int i1;in;i)fa[i]i;ll ans0;for(int i1;icnt;i){int fxFind_fa(te[i].u),fyFind_fa(te[i].v);if(fx!fy) fa[fy]fx,anste[i].w;}coutans;return 0;
}
