首页 > 代码库 > HDU 4424 Conquer a New Region 最大生成树
HDU 4424 Conquer a New Region 最大生成树
给你一颗树 每条边有一个权值 选择一个点为中心 定义S值为中心到其他n-1个点的路径上的最小边权 求所有点S值的和
从大到小排序 每次合并2棵树 设为A集合 B集合 设A集合的最大S值的和为sumA B集合为sumB
中心在A或者B现在加入A-B这条边使得2个集合连通 因为A-B这条边的权值小于等于AB集合里面边的权值 所以如果合并之后中心在A 那么sumA = sumA+B集合的点数*A-B这条边的权值 sumB = sumB+A集合的点数*A-B这条边的权值 2者取大
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <cmath> using namespace std; const int maxn = 200010; int n; int f[maxn], rank[maxn]; __int64 sum[maxn]; struct edge { int u, v, w; }e[maxn]; int find(int x) { if(x != f[x]) return f[x] = find(f[x]); return f[x]; } bool cmp(edge a, edge b) { return a.w > b.w; } int main() { while(scanf("%d", &n) != EOF) { for(int i = 0; i < n-1; i++) scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w); sort(e, e+n-1, cmp); for(int i = 0; i <= n; i++) f[i] = i, sum[i] = 0, rank[i] = 1; for(int i = 0; i < n-1; i++) { int x = find(e[i].u); int y = find(e[i].v); if(x != y) { if(sum[x]+(__int64)e[i].w*rank[y] > sum[y]+(__int64)e[i].w*rank[x]) { f[y] = x; sum[x] = sum[x]+(__int64)e[i].w*rank[y]; rank[x] += rank[y]; } else { f[x] = y; sum[y] = sum[y]+(__int64)e[i].w*rank[x]; rank[y] += rank[x]; } } } int x = find(1); printf("%I64d\n", sum[x]); } return 0; }
HDU 4424 Conquer a New Region 最大生成树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。