首页 > 代码库 > hdu 4424 Conquer a New Region (并查集)
hdu 4424 Conquer a New Region (并查集)
///题意:给出一棵树,树的边上都有边权值,求从一点出发的权值和最大,权值为从一点出去路径上边权的最小值 # include <stdio.h> # include <algorithm> # include <iostream> # include <string.h> using namespace std; # define MAX 200010 struct node { int u,v; int w; }; struct node a[MAX]; __int64 dis[MAX];///存以i为根结点的边权和 int father[MAX],rank[MAX];///存以i为根结点的数的节点数 void init()///初始化 { for(int i=0; i<=MAX; i++) { father[i]=i; rank[i]=1; dis[i]=0; } } int cmp(node a1,node a2)///边权从大到小 { return a1.w>a2.w; } int find(int x) { if(x==father[x]) return x; return father[x]=find(father[x]); } void Union(int x,int y,__int64 v) { father[x]=y; rank[y]+=rank[x]; dis[y]=v; } int main() { int i,n; __int64 s1,s2; while(~scanf("%d",&n)) { for(i=1; i<n; i++) scanf("%d%d%d",&a[i].v,&a[i].u,&a[i].w); init(); sort(a+1,a+n,cmp);/// for(i=1; i<n; i++) { int fa=find(a[i].v); int fb=find(a[i].u); if(fa!=fb)///树中不会出现fa,fb相等的情况。。。。 { s1=dis[fa]+a[i].w*rank[fb];///在fa集合中选点 s2=dis[fb]+a[i].w*rank[fa];///在fb集合中选点 } if(s1>s2) Union(fb,fa,s1); else Union(fa,fb,s2); } printf("%I64d\n",dis[find(1)]); } return 0; }
hdu 4424 Conquer a New Region (并查集)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。