首页 > 代码库 > [最小生成树]vijos1579 宿命的PSS
[最小生成树]vijos1579 宿命的PSS
题目梗概
输入给出最小生成树，由最小生成树求出最小完全图（任意两点之间只有一条线段相连）。
思考
首先一个图中最小生成树，按照kruskal算法。一定是使图连通的最小边。我们设这两点的边权为W，那么与两点相连的其他的边一定是W+1。
所以构建方法是 每次选出图中最短的边，其两点标记为A,B，边权为W，则与A,B连通的点边权修改为W+1。
#include <cstdio>#include <algorithm>typedef long long ll;int n;ll num[20005],fa[20005],ans; //num用来统计联通快的数量struct node{ ll u,v,w;}e[20005];bool CMP(const node &a,const node&b){ return a.w<b.w;}ll find(int x){ if(x!=fa[x]) fa[x] = find(fa[x]); return fa[x];}void merge(int x,int y,int z){ x = find(x); y = find(y); ans += (num[x]*num[y]-1) * (z+1); //这里是核心 fa[y]=x; num[x]+=num[y];}void Run(){ for(int i=1;i<=n;i++){ fa[i]=i; num[i]=1; } for(int i=1;i<n;i++){ ans+=e[i].w; //加上两点的边 merge(e[i].u,e[i].v,e[i].w); }}void init(){ scanf("%d",&n); for(int i=1;i<n;i++){ scanf("%lld%lld%lld",&e[i].u,&e[i].v,&e[i].w); } std::sort(e+1,e+n,CMP);}int main(){ init(); Run(); printf("%lld\n",ans); return 0;}
[最小生成树]vijos1579 宿命的PSS
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。