HDU 6326.Problem H. Monster Hunter-贪心(优先队列)+流水线排序+路径压缩、节点合并(并查集) (2018 Multi-University Training Contest 3 1008)

题意就是打怪兽，给定一棵 n 个点的树，除 1 外每个点有一只怪兽，打败它需要先消耗 ai点 HP，再恢复 bi点 HP。求从 1 号点出发按照最优策略打败所有怪兽一开始所需的最少 HP。

直接贴官方题解吧，这个题写的脑壳疼。

官方题解:

其实就是一直合并节点，最后合并到只有一个节点就是结果，具体的不想说什么了，这个题看了好久了，不想再看到他了。。。

代码是个人理解+个人习惯+综合多个题解写的。mdzz，我要撞墙。。。

代码:

 1 //1008-6326-贪心模拟+并查集+堆(优先队列)优化父亲节点
 2 //因为对于同一层而言，只是比较谁的a小，谁的b大，不同层，需要先ko掉父亲再找儿子才可以，这种情况就需要判断一下。
 3 #include<iostream>
 4 #include<cstdio>
 5 #include<cstring>
 6 #include<cmath>
 7 #include<algorithm>
 8 #include<queue>
 9 using namespace std;
10 typedef long long ll;
11 const int maxn=2e5+10;
12 struct node{
13     int u,num;
14     ll a,b;
15 
16     bool operator< (const node &x) const {//流水线排序         因为是优先队列，和正常的排序是反的
17         if(a>=b&&x.a< x.b) return true;
18         if(a< b&&x.a>=x.b) return false;
19         if(a< b&&x.a< x.b) return a>x.a;//对于a< b的，按照a从小到大
20         if(a>=b&&x.a>=x.b) return b<x.b;//对于a>=b的，按照b从大到小
21     }
22     void operator+=(const node &x){//节点合并，节点a表示至少需要a的血量杀死这个怪物
23         ll A=max(a,a-b+x.a);
24         ll B=b-a+x.b-x.a+A;
25         a=A,b=B;
26     }
27     
28 }a[maxn];
29 
30 priority_queue<node> q;
31 vector<int> g[maxn];
32 int fa[maxn],del[maxn],vis[maxn];
33 
34 void init(int n)//初始化
35 {
36     while(!q.empty()) q.pop();
37     for(int i=0;i<=n;i++){
38         vis[i]=0;del[i]=0;
39         g[i].clear();
40         a[i].a=a[i].b=0;
41         a[i].u=a[i].num=0;
42         a[i].u=i;
43     }
44 }
45 
46 void dfs(int u,int father)
47 {
48     fa[u]=father;
49     for(int i=0;i<g[u].size();i++){
50         int v=g[u][i];
51         if(v!=father)
52             dfs(v,u);
53     }
54 }
55 
56 int Find(int u)//并查集路径压缩
57 {
58     if(del[fa[u]])//父亲被删除，就找爷爷
59         return fa[u]=Find(fa[u]);
60     else
61         return fa[u];
62 }
63 
64 int main()
65 {
66     int t;scanf("%d",&t);
67     while(t--){
68         int n; scanf("%d",&n);
69         init(n);
70         for(int i=2;i<=n;i++){
71             scanf("%lld%lld",&a[i].a,&a[i].b);
72             a[i].u=i;a[i].num=0;
73             q.push(a[i]);
74         }
75         for(int i=1;i<n;i++){
76             int u,v;
77             scanf("%d%d",&u,&v);
78             g[u].push_back(v);
79             g[v].push_back(u);
80         }
81         dfs(1,0);
82         int pos=0;
83         while(!q.empty()){
84             node t=q.top();q.pop();
85             if(del[t.u]||t.num!=vis[t.u])continue;//如果节点删除或者节点已经被更新
86             del[t.u]=1;//删除该点
87             int f=Find(t.u);//找父节点
88             a[f]+=a[t.u];
89             if(f>1){
90                 a[f].num=vis[f]=++pos;//更新f节点(找到的父亲节点)
91                 q.push(a[f]);
92             }
93         }
94         printf("%lld
",a[1].a);
95     }
96     return 0;
97 }

关于结构体里面的排序，我以前写过一篇垃圾博客，可以看一下，有错的，可以锤我。。。

结构体内嵌比较函数bool operator < (const node &x) const {}

滚了滚了000OOOooo。。。...