1442 字
7 分钟
可持久化左偏树
1. 回顾左偏树的合并过程
假设我们要合并分别以 为根节点的两棵左偏树,且维护的左偏树满足小根堆的性质:
- 若为空则返回:如果 中有结点为空,返回 。
- 确定根节点:选择 两结点中权值更小的结点,作为合并后左偏树的根。
- 递归合并:递归合并 的右子树与 ,将合并后的根节点作为 的右儿子。
- 维护性质:维护当前合并后左偏树的左偏性质,维护
dist值,返回选择的根节点。
时间复杂度分析
由于每次递归都会使 dist[x] + dist[y] 减少一,而 dist[x] 是 的,一次最多只会修改 个结点,所以这样操作的时间复杂度是 。
2. 可持久化左偏树
可持久化要求保留历史信息,使得之后能够访问之前的版本。要将左偏树可持久化,就要将其沿途修改的路径复制一遍(路径复制)。
可持久化合并过程
- 若为空则返回:如果 中有结点为空,返回 。
- 新建副本:选择 两结点中权值更小的结点,新建该结点的一个复制 ,作为合并后左偏树的根。
- 递归合并:递归合并 的右子树与 ,将合并后的根节点作为 的右儿子。
- 维护性质:维护以 为根的左偏树的左偏性质,维护其
dist值,返回 。
复杂度分析
- 空间与时间复杂度:由于左偏树一次合并最多只会修改并新建 个结点,设操作次数为 ,则可持久化左偏树的时间复杂度和空间复杂度均为 。
复制于OIWIKI
P2483 【模板】k 短路 / [SDOI2010] 魔法猪学院
原始的A*算法为,我们对于每条路径,先后扩展之后都按照估价函数压入优先队列中,会发现其中许多路径具有重叠部分,每次扩展都会再次被压入,极大浪费了空间和时间,因此我们将问题进行一个转化. 考虑一个任意一条从起点s到t的一条路径,这条路径一定是经过若干最短路树上的边和非最短路树上的边,显然如果全走最短路树上的边一定是最短路,同时任意两点之间也一定存在一条非最短路树上的路径(树上的路径唯一性),形式化的,一条任意路径可以由一个边序列如下描述:
- 不在最短路上
- ,,,在最短路树上是的祖先 我们令,那么这条路径的长度 我们在每个结点都开一个堆,存储从这个结点出发的所有非最短路上的边,在堆内按照排序,那么对于当前的序列,我们有两种扩展方式:
- 移动到所在堆并取出最大元素 ,序列变成
- 将当前序列的末尾元素替换,已知当前序列在所在堆,继续取出更大的非树边替换掉末尾元素,序列变成 能保证不重不漏的扩展出所有状态.
代码
#include <bits/stdc++.h>#include <queue>#include <utility>#define ll long long#define N 4000005#define MAX 5005#define inf 2e12#define pr pair<ll, int>using namespace std;ll k, n, q, m, ans;ll E;class mergeable_heap { public: struct node { ll val = 0; int ls = 0, rs = 0, dis = 0, pos = 0; } tr[N]; int id = 0; mergeable_heap() { tr[0] = {0, 0, 0, -1, 0}; } int new_(pr x) { tr[++id].val = x.first; tr[id].pos = x.second; // 注意不要++两次 return id; } int clone(int x) { tr[++id] = tr[x]; return id; }#define lc tr[x] .ls#define rc tr[x] .rs int merge(int x, int y) { if (!x || !y) return x + y; if (make_pair(tr[x].val, x) > make_pair(tr[y].val, y)) swap(x, y); x = clone(x); rc = merge(rc, y); if (tr[lc].dis < tr[rc].dis) swap(lc, rc); tr[x].dis = tr[rc].dis + 1; return x; } int del(int x) { return merge(lc, rc); } auto get_val(int x) { return tr[x].val; }#undef lc#undef rc} mh;vector<vector<tuple<int, ll, int>>> rev_map1;vector<vector<tuple<int, ll, int>>> map1;vector<int> pre;vector<int> root;vector<ll> dis;vector<tuple<int, int, ll>> edges;int main() { ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); long double ee; cin >> n >> m >> ee; E = (ll)(ee * (10000.0) + 0.5); rev_map1.assign(n + 5, {}); map1.assign(n + 5, {}); dis.assign(n + 5, inf); root.assign(n + 5, 0); pre.assign(n + 5, -1); for (int i = 1; i <= m; i++) { ll a, b, c; long double cc; cin >> a >> b >> cc; c = (ll)(cc * (10000.0) + 0.5); edges.push_back({a, b, c}); rev_map1[b].push_back({a, c, edges.size() - 1}); map1[a].push_back({b, c, edges.size() - 1}); } auto dij = [&](int st) { vector<bool> vis(n + 5, 0); priority_queue<pr> q; q.push({0, st}); dis[st] = 0; while (q.size()) { auto [_, x] = q.top(); q.pop(); if (vis[x]) continue; vis[x] = 1; for (auto [v, w, id] : rev_map1[x]) { if (dis[v] > dis[x] + w) { dis[v] = dis[x] + w; pre[v] = id; q.push({-dis[v], v}); } } } }; dij(n); vector<ll> s; for (int i = 1; i <= n; i++) s.push_back(i); sort(s.begin(), s.end(), [&](int x, int y) { return dis[x] < dis[y]; }); auto build = [&]() { for (auto now : s) { if (dis[now] >= inf || now == n) continue; // 很重要!!改了半天才发现这里的问题,到达n之后就不需要再往祖先走了 if (pre[now] != -1) { int from = get<1>(edges[pre[now]]); root[now] = root[from]; } for (auto [v, w, id] : map1[now]) { if (id == pre[now]) continue; root[now] = mh.merge(root[now], mh.new_({w - dis[now] + dis[v], id})); } } }; build();#define lc mh.tr[rt] .ls#define rc mh.tr[rt] .rs auto astar = [&](int st) { priority_queue<pr> q; if (dis[st] < inf && E >= dis[st]) { E -= dis[st]; ans++; if (root[st]) q.push({-(dis[st] + mh.get_val(root[st])), root[st]}); } while (q.size()) { auto [cost, rt] = q.top(); cost = -cost; q.pop(); if (cost > E) break; E -= cost; ans++; if (lc) { q.push({-(cost - mh.get_val(rt) + mh.get_val(lc)), lc}); } if (rc) { q.push({-(cost - mh.get_val(rt) + mh.get_val(rc)), rc}); } int v = get<1>(edges[mh.tr[rt].pos]); if (root[v]) { q.push({-(cost + mh.get_val(root[v])), root[v]}); } } }; astar(1); cout << ans; return 0;}分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 74 天
部分内容可能已过时