zoj 2334 Monkey King/左偏樹+並查集，zoj2334
原題鏈接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1389
大致題意：N只相互不認識的猴子(每只猴子有一個戰斗力值)
兩只不認識的猴子之間發生沖突，兩只猴子會分別請出它們認識的最強壯的
猴子進行決斗。決斗之後這，兩群猴子都相互認識了。
決斗的那兩只猴子戰斗力減半。。。有m組詢問
輸入a b表示猴子a和b發生了沖突，若a,b屬於同一個集合輸出-1
否則輸出決斗之後這群猴子(已合並)中最強的戰斗力值。。。
具體思路：用並查集判斷是否屬於同一集合，用左偏樹維護一群猴子的戰斗力值。
加了垃圾回收，否則容易爆內存。。。
具體如下：
![]()
1 #include<cstdio>
2 #include<cstdlib>
3 #include<iostream>
4 #include<algorithm>
5 const int Max_N = 100050;
6 struct UnionFind{
7 int par[Max_N], rank[Max_N];
8 inline void init(int n){
9 for (int i = 1; i <= n; i++){
10 par[i] = i;
11 rank[i] = 0;
12 }
13 }
14 inline int find(int x){
15 while (x != par[x]){
16 x = par[x] = par[par[x]];
17 }
18 return x;
19 }
20 inline void unite(int x, int y){
21 x = find(x), y = find(y);
22 if (x == y) return;
23 if (rank[x] < rank[y]){
24 par[x] = y;
25 } else {
26 par[y] = x;
27 if (rank[x] == rank[y]) rank[x]++;
28 }
29 }
30 };
31 struct Node{
32 int v, npl;
33 Node *ch[2];
34 inline void set(int _v = 0, int _npl = -1, Node *p = NULL){
35 v = _v, npl = _npl;
36 ch[0] = ch[1] = p;
37 }
38 inline void push_up(){
39 npl = ch[1]->npl + 1;
40 }
41 };
42 struct LeftistTree{
43 int N, top;
44 UnionFind rec;
45 Node *tail, *null;
46 Node stack[Max_N], *ptr[Max_N], *store[Max_N];
47 void init(int n){
48 tail = &stack[0];
49 null = tail++;
50 null->set();
51 N = n, top = 0, rec.init(n);
52 }
53 inline Node *newNode(int v){
54 Node *p = null;
55 if (!top) p = tail++;
56 else p = store[--top];
57 p->set(v, 0, null);
58 return p;
59 }
60 inline Node* Merge(Node* &x, Node* &y){
61 if (x == null) return y;
62 if (y == null) return x;
63 if (y->v > x->v) std::swap(x, y);
64 x->ch[1] = Merge(x->ch[1], y);
65 if (x->ch[1]->npl > x->ch[0]->npl)
66 std::swap(x->ch[0], x->ch[1]);
67 x->push_up();
68 return x;
69 }
70 inline int get_max(int i){
71 return ptr[i]->v;
72 }
73 inline void insert(){
74 int v;
75 for (int i = 1; i <= N; i++){
76 scanf("%d", &v);
77 ptr[i] = newNode(v);
78 }
79 }
80 inline void del(int i){
81 int ret = get_max(i);
82 Node *x = newNode(ret >> 1);
83 store[top++] = ptr[i];
84 ptr[i] = Merge(ptr[i]->ch[0], ptr[i]->ch[1]);
85 ptr[i] = Merge(ptr[i], x);
86 }
87 inline void gogo(int a, int b){
88 int ans = 0;
89 a = rec.find(a), b = rec.find(b);
90 if (a == b){
91 printf("-1\n");
92 return;
93 }
94 rec.unite(a, b);
95 del(a), del(b);
96 if (rec.rank[a] > rec.rank[b]){
97 ptr[a] = Merge(ptr[a], ptr[b]);
98 ans = ptr[a]->v;
99 } else {
100 ptr[b] = Merge(ptr[a], ptr[b]);
101 ans = ptr[b]->v;
102 }
103 printf("%d\n", ans);
104 }
105 }lft;
106 int main(){
107 #ifdef LOCAL
108 freopen("in.txt", "r", stdin);
109 freopen("out.txt", "w+", stdout);
110 #endif
111 int n, m, a, b;
112 while (~scanf("%d", &n)){
113 lft.init(n), lft.insert();
114 scanf("%d", &m);
115 while (m--){
116 scanf("%d %d", &a, &b);
117 lft.gogo(a, b);
118 }
119 }
120 return 0;
121 }
View Code
