Skew Heap
Skew Heap は, meld (2 つのpriority queue をmerge する操作) ができるheapです.
meld ができると,
push は, 新しい要素をヒープとして親とmeld,
pop は 親の子をmeld
で実装できてしまいます.
計算量はならしO(log N) で便利です.
(くわしくはhos さんのブログ などを参照してください.)
これをつかって, AOJ 0542 (Authentication Level) を解いてみました. なかなか高速です.
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; struct Heap { Heap *l, *r; int val; int pos; Heap(int val, int pos) : val(val), pos(pos){ l = r = (Heap *)0; } }; Heap *root; Heap *meld(Heap *a, Heap *b) { if (!a) return (b); if (!b) return (a); if (a->val > b->val) swap(a, b); a->r = meld(a->r, b); swap(a->l, a->r); return (a); } void push(Heap x) { Heap *p = new Heap(x); root = meld(root, p); } Heap top() { return (*root); } void pop() { Heap *p = root; root = meld(root->r, root->l); delete p; } int reqLevel[2][500 * 500 + 1]; int map[512][512]; bool visited[512][512]; int dy[] = {1, 0, -1, 0}; int dx[] = {0, 1, 0, -1}; int main() { int R; while (scanf("%d", &R) && R){ for (int t = 0; t < 2; t++){ int W, H, Sx, Sy; scanf("%d %d %d %d", &W, &H, &Sx, &Sy); for (int i = 1; i <= R; i++){ reqLevel[t][i] = 1000000000; } for (int i = 0; i < H; i++){ for (int j = 0; j < W; j++){ scanf("%d", &map[i][j]); } } memset(visited, 0, sizeof(visited)); --Sy; --Sx; push(Heap(map[Sy][Sx], Sy * 1000 + Sx)); int req = 0; int num = 0; while (root){ Heap x = top(); pop(); if (visited[x.pos / 1000][x.pos % 1000]) continue; visited[x.pos / 1000][x.pos % 1000] = true; req = max(req, x.val); reqLevel[t][++num] = req; for (int i = 0; i < 4; i++){ int ny = x.pos / 1000 + dy[i], nx = x.pos % 1000 + dx[i]; if (0 <= ny && ny < H && 0 <= nx && nx < W){ push(Heap(map[ny][nx], ny * 1000 + nx)); } } } } int ans = 2000000000; for (int i = 0; i <= R; i++){ ans = min(ans, reqLevel[0][i] + reqLevel[1][R - i]); } printf("%d\n", ans); } return (0); }