HDOJ 1512 Monkey King -- 左偏树

news/2024/11/18 0:48:01/

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1512

分析：左偏树应用。在结点中加入了parent指针和id字段，这样可以代替并查集。关于左偏树可以参考黄源河的论文《左偏树的特点及其应用》。

#include #include #include #include #include #include  #include #include #include #include #include #include #include #include #include #include #define mp make_pair #define X first #define Y second #define MEMSET(a, b) memset(a, b, sizeof(a)) using namespace std; typedef unsigned int ui; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef vector vi; typedef vi::iterator vi_it; typedef map mii; typedef priority_queue pqi; typedef priority_queue , greater > rpqi; typedef priority_queue pqp; typedef priority_queue , greater > rpqp; typedef struct node { int key; int dist; int id; node *left; node *right; node *parent; } *pnode; const int MAX_N = 100000 + 2; pnode mk[MAX_N]; pnode hd[MAX_N]; class LeftistTree { public: pnode merge(pnode a, pnode b) { if (a == NULL) { return b; } if (b == NULL) { return a; } if (a->key < b->key) { swap(a, b); } a->right = merge(a->right, b); a->right->parent = a; if (a->left == NULL || a->left->dist < a->right->dist) { swap(a->right, a->left); } if (a->right == NULL) { a->dist = 0; } else { a->dist = a->right->dist + 1; } a->parent = NULL; return a; } int get_max(const pnode &a) { return a->key; } void decrease_key(pnode a) { pii maxv = del_max(a); ins(a, maxv.X >> 1, maxv.Y); } pnode new_node(int key, int id) { pnode p = new node(); p->left = p->right = p->parent = NULL; p->key = key; p->id = id; p->dist = 0; return p; } pnode get_root(pnode p) { while (p->parent != NULL) { p = p->parent; } return p; } void clear_tree(pnode root) { if (root == NULL) { return; } clear_tree(root->left); clear_tree(root->right); delete root; } private: pii del_max(pnode &a) { pii ret = mp(a->key, a->id); pnode b = a; a = merge(a->left, a->right); delete b; return ret; } void ins(pnode &a, int key, int id) { mk[id] = new_node(key, id); a = merge(a, mk[id]); } }; int main(int argc, char *argv[]) { // freopen("D:\\in.txt", "r", stdin); int n, m, i, k, a, b; LeftistTree lft; while (cin >> n) { for (i = 1; i <= n; ++i) { scanf("%d", &k); mk[i] = lft.new_node(k, i); } cin >> m; while (m--) { scanf("%d%d", &a, &b); pnode h1 = lft.get_root(mk[a]), h2 = lft.get_root(mk[b]); if (h1 == h2) { puts("-1"); } else { lft.decrease_key(h1); lft.decrease_key(h2); h1 = lft.get_root(mk[a]); h2 = lft.get_root(mk[b]); pnode h = lft.merge(h1, h2); printf("%d\n", lft.get_max(h)); } } int cnt = 0; for (i = 1; i <= n; ++i) { if (mk[i] != NULL && mk[i]->parent == NULL) { hd[cnt++] = mk[i]; } } for (i = 0; i < cnt; ++i) { lft.clear_tree(hd[i]); } } return 0; }

HDOJ 1512 Monkey King -- 左偏树

相关文章

第 197 场周赛 leetcode 1512. 好数对的数目 1513. 仅含 1 的子串数 1514. 概率最大的路径

一文看尽深度学习中的20种卷积（附源码整理和论文解读）

ZYNQ Linux 双网口，MDIO共用，RESET-GPIO不共用

supersocket client 固定端口_西门子CPU控制器1512P-1PN端口交换机附件200KB

【HDOJ】1512 Monkey King

力扣1748，387，1941，448，1512，1711题解

CF1512E Permutation by Sum（思维）

1512 好数对的数目