各种优化建图、最短路建模技巧
直接看题吧，思路有了，但是有些题代码没打。兔子正在加油中。优化建图
I.（线段树）CF786B Legacy
题目描述三种连边操作，执行 \(q(1\le n\le10^5)\) 次：
[*]\(x\xrightarrow{w}y\)
[*]\(x\xrightarrow{w}y,y\in\)
[*]\(x\xrightarrow{w}y,x\in\)
求 \(s\) 到其余点的最短路。
暴力连边肯定不行。
有没有什么东西是把一个区间拆分成 \(\log\) 个的？
当然是线段树优化建图啦。因为加入的是一个区间，所以用线段树上的 \(\log\) 个结点来表示区间，对这些结点连边。
对于 \( \to v\)，把 \(\log\) 个结点连向线段树上的 \(v\)，之后把线段树本身连成一颗内向树。
对于 \( \gets v\)，在对线段树内部连边时，显然不能和上一种情况连同一些结点，不然最短路都是 \(0\)。于是重新开一颗线段树，把这个颗树连成外向树。对于这颗线段树上的 \(\log\) 个结点，连向上内向树上的 \(v\)。
这两颗树上的叶子在原图上是同一个点，所以这两颗树的叶子要连权值为 \(0\) 的边（显然只需要外向树向内向树连边）。
对于建出来的图跑最短路，有 \(n\) 个结点 \(m\log n\) 条边，堆优化 Dijkstra 时间复杂度 \(\mathcal{O}(m\log_2 n)\)。
CF786B#include#define int long long#define endl '\n'#define pi pairusing namespace std;const int N=3e6+10,K=5e5;int n, m, s, op, a, d;bool vis;priority_queue q;int pre, cnt;struct node{ int to, next, l;}g;void add(int u,int v,int l){ g[++cnt] = {v, pre, l}; pre = cnt; return ;}struct Segment_Tree{#define ls (k > 1; add(k, ls, 0); add(k, rs, 0); add(ls + K, k + K, 0); add(rs + K, k + K, 0); build(ls, l, mid); build(rs, mid+1, r); } void modify(int k, int l, int r, int lx, int rx, int v, int w){ if(l >= lx && r > 1; if(lxmid) modify(rs, mid+1, r, lx, rx, v, w); return ; }}tree;inline void dijkstra(int s){ memset(d, 0x3f, sizeof d); d = 0; q.push(make_pair(0, s)); while(q.size()){ int x = q.top().second; q.pop(); if(vis) continue; vis = true; for(int i = pre; i; i = g.next){ int to = g.to, l = g.l; if(d > d + l) { d = d + l; q.push(make_pair(-d, to)); } } } return ;}inline int read(){ int x; cin >> x; return x;}signed main(){ cin.tie(nullptr)->sync_with_stdio(false); n = read(), m = read(), s = read(); tree.build(1, 1, n); for(int i = 1; i
页:
[1]