最近好多题目都是树型结构,我最开始想到的是树型dp,但是完全没有思路,结题报告给的是并查集,看着解题报告想了好久,才看懂什么意思。
按边排序,从大到小插入,每条边将两个集合连起来,而新加的边是两个集合所有边最小的,那么两个集合中的点交叉的通路最小的边就是新加的,那只要枚举两个集合,a,b是a并入b更优还是b并入a更优就行了。集合内部点已经计算出,相互的只要知道集合中元素的个数就好了。
所以并查集只需要维护一个集合的元素个数,一个集合的总权值。
code:
/** 并查集问题,我从来没有遇到这么难的!! 也是kruscal的变形吧? */ #include <iostream> #include <string.h> #include <stdio.h> #include <algorithm> using namespace std; #define N 200010 struct note { int a,b,c; }dat[N]; bool cmp(const note a,const note b) { return a.c > b.c; } struct node { int index; long long val,size; }nod[N]; void init(int n) { for(int i = 0;i <= n;i++) { nod[i].index = i; nod[i].size = 1; nod[i].val = 0; } } int fa(int n) { while(nod[n].index != n) n = nod[n].index; return n; } int main() { int n; while(scanf("%d",&n) != EOF) { for(int i = 0;i < n - 1;i++) scanf("%d%d%d",&dat[i].a,&dat[i].b,&dat[i].c); sort(dat,dat+n-1,cmp); init(n); for(int i = 0;i < n-1;i++) { int a = dat[i].a; int b = dat[i].b; long long c = dat[i].c; int _a = fa(a); int _b = fa(b); long long _v = max(nod[_a].val + nod[_b].size*c,nod[_a].size*c + nod[_b].val); nod[_a].index = _b; nod[_b].size += nod[_a].size; nod[_b].val = _v; //cout << _b << " " << nod[_b].size << " " << _v << " \n"; } printf("%lld\n",nod[fa(1)].val); } return 0; }