当前位置: 首页 > news >正文

10.16 闲话-k 短路

10.16 闲话-k 短路

Part.1 左偏树

左偏树是一个堆,支持 \(O(\log n)\) 合并。

假设 \(dist_i\) 表示离 \(i\) 最近的儿子数量不为 \(2\) 的儿子的距离 + 1,孤立点设为 0。

容易发现 \(dist_i \le \log n\)

证明考虑如果有 \(dist_i\) 则树高一定大于了 \(2^{dist_i-1}\)

那么如果钦定每一个节点的右儿子 \(dist\) 小于左儿子 \(dist\) ,那么这棵树就是左偏树。

不难发现此时 \(dist_i=dis_{rs_i}+1\)

故左偏树任意节点右链是 \(O(\log n)\) 的!

此时就很暴力了,合并时考虑将两个树树根较小的作为新的跟,然后将另一个跟和右儿子合并作为新的右儿子,注意此时可能破坏左偏结构,需要判断是否要交换左右儿子。

发现复杂度是 \(O(\log n)\)

int Merge(int x, int y)
{if (!x || !y) return x | y;if (val[x] > val[y]) swap(x, y);rs[x] = Merge(rs[x], y);fa[rs[x]] = x;if (dis[rs[x]] > dis[ls[x]]) swap(ls[x], rs[x]);dis[x] = dis[rs[x]] + 1;return x;
}

删除也很暴力,直接合并左右儿子,然后自底向上更新 \(dis\),由于可能发生更新的都是右儿子,而右链长度是 \(O(\log n)\) 的,所以复杂度是 \(O(\log n)\) 的。

void PushUp(int x)
{if (!x) return ;if (dis[x] != dis[rs[x]] + 1){dis[x] = dis[rs[x]] + 1;PushUp(fa[x]);}
}void Delete(int x)
{int y = Merge(ls[x], rs[x]);fa[y] = fa[x];if (ls[fa[x]] == x) ls[fa[x]] = y;if (rs[fa[x]] == x) rs[fa[x]] = y;if (dis[rs[fa[x]]] > dis[ls[fa[x]]]) swap(ls[fa[x]], rs[fa[x]]);PushUp(fa[y]);
}

然后其实就没了,会了这些,加上一些高端的并查集应用,就可以过穿可并堆的题目了。

Part.2 可持久化可并堆

发现上述过程完美符合可持久化操作,只需要 Merge 时新建一个节点即可。


int Merge(int x, int y)
{if (!x || !y) return x | y;if (val[x] > val[y]) swap(x, y);int p = ++cnt;ls[p] = ls[x], val[p] = val[x];rs[p] = Merge(rs[x], y);fa[rs[p]] = p;if (dis[rs[p]] > dis[ls[p]]) swap(ls[p], rs[p]);dis[p] = dis[rs[p]] + 1;return p;
}

Part.3 k 短路

会了一些前置知识后就可以开始学习 k 短路了。

其实我们可以发现一件事情就是一条更劣的路一定是经过了一些最短路的边,然后经过一些不在最短路上的边。

那么可以先建出到终点的最短路树(假设每个点到终点的距离为 \(h_i\)),然后将不在树边上的边成为偏离边。

这时发现经过一个偏离边(假设边权为 \(w\))的增加的代价其实就是 \(w+h_{to}-h_{from}\)

由于这是有向图,那么可以得知,对于一个路径,相邻的非树边中上一条的终点一定是这条边起点的儿孙。

那么便可以将一条边终点不变的添加到起点的子树中,将问题转化为统计从 \(s\) 到任意节点的 \(k\) 短路。

这时又注意到,对于每个要去转移的节点,如果其边越小转移出去越优,那么每次只更新最小的边,然后将这条边删去,发现这是一个堆能干的(每次拿出一个堆,弹掉栈顶)。

此时就发现,原本放到子树中的那一步操作竟然可以可持久化可并堆。

这样就愉快的通过了 k 短路。

复杂度 \(O((n+m)\log m+k\log k)\)

code
#include <iostream>
#include <cassert>
#include <vector>
#include <cstring>
#include <queue>
#include <climits>using namespace std;const int N = 2e6 + 10, M = 6000;#define fi first
#define se second
#define emp emplace_backusing ld = double;
using pii = pair <int, int>;
const ld inf = 1e300, eps = 1e-9;int cnt, ls[N], rs[N], rt[M], to[N], d[N], pre[M];
ld val[N];int Merge(int x, int y)
{if (!x || !y) return x | y;if (val[x] > val[y]) swap(x, y);int p = ++cnt;ls[p] = ls[x], val[p] = val[x], to[p] = to[x];rs[p] = Merge(rs[x], y);if (d[ls[p]] < d[rs[p]]) swap(ls[p], rs[p]);d[p] = d[rs[p]] + 1;return p;
}int New(ld v, int _to) {++cnt; val[cnt] = v, to[cnt] = _to; return cnt;}void Insert(int &x, ld v, int to)
{x = Merge(x, New(v, to));
}int n, m;
ld dis[M], pw[M];
vector <pair <int, ld>> E[M], T[M], NT[M];void dfs(int x, int fa)
{for (auto [to, w] : NT[x]) Insert(rt[x], w, to);rt[x] = Merge(rt[x], rt[fa]);for (auto [to, w] : T[x]){if (to == fa) continue;dfs(to, x);}
}int Solve(int s, ld k)
{priority_queue <pair <ld, int>> q;q.push({-(dis[s] + val[rt[s]]), rt[s]});int timer = 0;++timer, k -= dis[s];if (k < 0) return 0;while (q.size()){int x = q.top().se;ld y = -q.top().fi; q.pop();if (!x) continue;k -= y, ++timer;if (k < 0) return timer - 1;q.push({-(y + val[rt[to[x]]]), rt[to[x]]});q.push({-(y - val[x] + val[ls[x]]), ls[x]});q.push({-(y - val[x] + val[rs[x]]), rs[x]});}return timer;
}bool vis[M];
void dij(int s)
{for (int i = 1; i <= n; i++) dis[i] = inf;priority_queue <pair <ld, int>> q;q.push({0, s});dis[s] = 0;while (q.size()){int x = q.top().se; q.pop();if (vis[x]) continue;vis[x] = 1;for (auto [to, w] : E[x]){if (dis[to] > dis[x] + w){pre[to] = x, pw[to] = w;dis[to] = dis[x] + w;q.push({-dis[to], to});}}}
}bool flag[M];signed main()
{// freopen("data.in", "r", stdin); freopen("data.out", "w", stdout);ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);ld k; cin >> n >> m >> k;for (int i = 1; i <= m; i++){int x, y; ld w; cin >> x >> y >> w;if (x == n) continue;E[y].emp(x, w);}dij(n);for (int i = 1; i <= n; i++){for (auto [to, w] : E[i]){if (pre[to] == i && abs(pw[to] - w) < eps && !flag[to]) flag[to] = 1, T[i].emp(to, w);else NT[to].emp(i, w + dis[i] - dis[to]);}}dfs(n, 0);cout << Solve(1, k) << '\n';return 0;
}
http://www.hskmm.com/?act=detail&tid=33435

相关文章:

  • 初次扫描设计
  • 关于虚数单位与复数
  • AI深度学习平台快速诊断肌张力障碍
  • 2025年多功能防水篷布厂家推荐排行榜,聚乙烯/帐篷/汽车/宴会/盖草布/泳池布/微喷水带/日用盖/农林用/重型机器用篷布公司精选
  • 2025年干燥机厂家推荐排行榜,小型喷雾/实验室离心喷雾/双锥回转真空/搪瓷双锥/旋转闪蒸/振动流化床/真空耙式/单层带式/多层带式/立式沸腾/卧式沸腾/滚筒刮板干燥机!
  • 2025年润滑油厂家推荐排行榜,工业/汽车/发动机/甲醇发动机润滑油,全合成/长效润滑油公司精选
  • 2025年数粒机厂家推荐排行榜,防爆/新型/高速/高精度/智能/大容量/多通道/电子/视觉/全自动/低噪音/制药/农业/食品/电子元件/光电/定制化/鹌鹑蛋/糖果/坚果/药品/片剂数粒机公司推荐
  • 2025年码垛机厂家推荐排行榜,多样板材/倒板/分拣/上料/下料码垛机,全自动/半自动/龙门/桁架/双工位/单工位/单立柱码垛机械手公司推荐!
  • 2025年CNC高压清洗机厂家推荐排行榜,CNC全自动高压清洗机,CNC去毛刺清洗机,工业CNC高压清洗机公司推荐!
  • 数字化ERP“一图四清单”战略执行体系 - 智慧园区
  • 因果分布变化解释方法解析
  • OAuth/OpenID Connect 渗透测试完整指南
  • 2025年塑料托盘厂家推荐排行榜,网格川字/九脚/田字/双面/平板/吹塑/注塑/焊接/印刷/组装款/高矮脚/反川字/立体库托盘公司精选
  • 2025年信息流代运营服务商权威推荐榜:精准投放与高效转化的首选!
  • 2025年铝单板厂家推荐排行榜,氟碳/木纹/冲孔/外墙/雕花/异形/双曲/弧形/雕刻铝单板公司精选
  • 2025年轻钢龙骨厂家,铝方通厂家,铝单板厂家,石膏板厂家权威推荐榜单:专业品质与市场口碑深度解析
  • 2025年解冻设备厂家推荐排行榜,低温高湿/静电解冻/射频解冻/速冻螺旋/缓化柜/复醒柜设备公司精选!
  • 2025年数控滚齿机厂家推荐排行榜,高速/高效/立式/卧式/直齿/斜齿/圆柱齿轮/锥形齿轮/涡轮蜗杆/花键轴/链轮/多联齿/小模数/大模数/高精度滚齿机公司推荐!
  • 2025年防腐木加工厂权威推荐榜:环保耐用,品质卓越的厂家精选!
  • 2025年防水连接器/航空插头/工业网线厂家推荐排行榜,专业品质与耐用性能的首选!
  • 2025年无锡公考/考编培训机构推荐榜单,事业单位/央企国企考编培训优选机构!
  • 2025年储罐源头厂家权威推荐榜单:钢衬塑/钢塑复合/化工/防腐/PE/盐酸/硫酸/聚丙烯/不锈钢/次氯酸钠储罐公司精选
  • 2025年铣刀厂家推荐排行榜,雕刻机/金刚石/木工/绝缘材料/碳纤维/亚克力/金属加工/铝合金/石墨/不锈钢/电木/塑胶/PC铣刀公司精选!
  • 2025年危险品运输公司权威推荐榜:安全高效与专业服务的首选!
  • 2025年彩钢瓦,镀锌板,折弯件,C型钢,Z型钢,压型瓦,楼承板,钢结构安装,次檩条厂家推荐排行榜,品质与服务双重保障!
  • 2025年发电机组厂家推荐排行榜,柴油/燃气/船用/静音箱式/移动拖车式/集装箱式,上柴/玉柴/潍柴/康明斯/沃尔沃/道依茨/帕金斯/MTU品牌精选!
  • 2025年粉末冶金制品/零件厂家推荐排行榜,高精度粉末冶金零件,耐磨粉末冶金制品公司推荐!
  • 2025年舒适耐磨轮胎厂家推荐排行榜,静音轮胎,耐用轮胎,高性能轮胎公司推荐!
  • 2025年爱采购代运营/店铺托管、网页/网站搭建设计开发推广服务商推荐排行榜,一站式网络营销解决方案!
  • 2025年齿轮减速机厂家推荐排行榜,R/K斜齿轮,F平行轴齿轮,S/RV蜗轮蜗杆,HB工业齿轮箱,B/BKM摆线针轮公司推荐!