首页 > 代码库 > HDU 4424 Conquer a New Region 并查集
HDU 4424 Conquer a New Region 并查集
题意:
给定一棵有边权的树。
设某个点x为中心,对于其他点y的权值为 x-y路径上最小的边权。
x作为中心的收益 为其他点的点权和。
问:
收益最大是多少。
按边排序然后并查集。。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> template <class T> inline bool rd(T &ret) { char c; int sgn; if (c = getchar(), c == EOF) return 0; while (c != '-' && (c<'0' || c>'9')) c = getchar(); sgn = (c == '-') ? -1 : 1; ret = (c == '-') ? 0 : (c - '0'); while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0'); ret *= sgn; return 1; } template <class T> inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if (x>9) pt(x / 10); putchar(x % 10 + '0'); } using namespace std; typedef long long ll; const int N = 200100; struct Edge{ int u, v, d; }edge[N]; bool cmp(const Edge &x, const Edge&y){ return x.d > y.d; } Edge add(int u, int v, int d){ Edge E = {u, v, d}; return E; } int n; int fa[N], num[N]; ll sum[N]; void init(){ memset(sum, 0, sizeof sum); for(int i = 1; i <= n; i++) fa[i] = i, num[i] = 1; } int find(int x){return x==fa[x]?x:fa[x] = find(fa[x]);} void Union(int x, int y, ll ans){ num[x] += num[y]; fa[y] = x; sum[x] += ans ; } ll work(){ for(int i = 1; i < n; i++) { int fx = find(edge[i].u); int fy = find(edge[i].v); ll a = (ll)num[fy]*(ll)edge[i].d + sum[fx]; ll b = (ll)num[fx]*(ll)edge[i].d + sum[fy]; if(a>b) Union(fx, fy, a-sum[fx]); else Union(fy, fx, b-sum[fy]); } return sum[find(1)]; } void input(){ for(int i = 1, u, v, d; i < n; i++) { rd(u); rd(v); rd(d); edge[i] = add(u,v,d); } sort(edge+1, edge+n, cmp); } int main(){ while (cin>>n){ init(); input(); cout<<work()<<endl; } return 0; }
HDU 4424 Conquer a New Region 并查集
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。