題意：給出一棵樹，樹的邊上都有邊權值，求從一點出發的權值和最大，權值為從一點出去路徑上邊權的最小值 ?

邊權從大到小排序后 ?每次合并

取總權值最大的為父親節點

#include <cstdio> #include <cstring> #include <cstdlib> #include <string> #include <iostream> #include <algorithm> #include <sstream> #include <cmath> using namespace std; #include <queue> #include <stack> #include <vector> #include <deque> #include <map> #define cler(arr, val) memset(arr, val, sizeof(arr)) typedef long long LL; const int MAXN = 555; const int MAXM = 260110; const int INF = 0x3f3f3f3f; const int mod = 1000000007; struct node {LL a1,b1;LL v; }; struct node a[200010]; LL father[200010],rank[200010]; LL dis[200010];///邊權和 LL n; bool cmp(node c1,node c2) {return c1.v>c2.v; } void init() {for(LL i=1; i<=n; i++){father[i]=i;dis[i]=0;rank[i]=1;///以i為根的節點數} } LL find(LL x) {if(x==father[x])return x;return father[x]=find(father[x]); } void Union(LL x,LL y,LL w) {father[x]=y;rank[y]+=rank[x];dis[y]=w; } int main() { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout); #endifLL x1,x2;while(~scanf("%lld",&n)){for(int i=1; i<n; i++)scanf("%lld%lld%lld",&a[i].a1,&a[i].b1,&a[i].v);init();sort(a+1,a+n,cmp);for(int i=1; i<n; i++){LL fa=find(a[i].a1);LL fb=find(a[i].b1);x1=dis[fa]+a[i].v*rank[fb];x2=dis[fb]+a[i].v*rank[fa];if(x1>x2)Union(fb,fa,x1);elseUnion(fa,fb,x2);}printf("%lld\n",dis[find(1)]);}return 0; }

轉載于:https://www.cnblogs.com/kewowlo/p/4088296.html

總結

以上是生活随笔為你收集整理的【并查集】 HDU 4424 Conquer a New Region 贪心的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。