前言
题目链接:Hydro & bzoj。
题意简述
无向联通图给出起点终点,多次询问删边后最短路,或报告不连通。
\(n, m, q \leq 2 \times 10^5\)。
题目分析
首先想到,如果删掉的边不是原来最短路的边,那么最短路不会发生变化。因此我们只需考虑删除了原来在最短路上的边。
不妨把原先最短路任选一条拉下来,记作 \(d_1 \ldots d_k\),其中 \(d_1 = s, s_k = t\)。设删除的边 \((u, v) = (d_{p}, d_{p+1})\)。
我们为了走到 \(t\),不得不经过一些更长的边。考虑以 \(s\) 为根,建出最短路径树。只进过树边到达不了 \(t\),所以要进过一些非树边,并且只经过一条非树边,因为经过更多的非树边是不优的。记这条非树边是 \(x \rightarrow y\),那么我们要找到 \(y \rightarrow t\) 的最短路径,这个以 \(t\) 为起点跑一边最短路即可。
所以,问题转化为,找到新的最短路 \(s \rightarrow d_{i} \rightarrow x \rightarrow y \rightarrow d_{j} \rightarrow t\),其中 \(i \leq p\) 并且 \(j \geq p + 1\)。那么 \(d_i\) 就是以 \(s\) 为根的最短路径树上,\(x\) 到链 \(s \sim t\) 的结点,\(d_j\) 是以 \(t\) 为根的最短路径树上, \(y\) 到链 \(s \sim t\) 的结点。
用 BFS 或 DFS 什么的标记一下预处理很方便。不妨把 \((x, y)\) 这条非树边挂在 \(d_i\) 上,记作二元组 \(v_i = (d_j, len)\),其中 \(len\) 是经过 \((x, y)\) 最短路长度。查询变成了在 \(v_{1 \sim p}\) 中,前者 \(\geq p + 1\) 的后者的最小值。
可以用堆,不断加入、删除,统计答案。
可以用线段树,把 \(i \sim j - 1\) 覆盖最小值。
可以用主席树,变成查询 \(p\) 版本 \(\geq p + 1\) 的最小值。
代码
使用了主席树,并略去了快读快写。
// #pragma GCC optimize(3)
// #pragma GCC optimize("Ofast", "inline", "-ffast-math")
// #pragma GCC target("avx", "sse2", "sse3", "sse4", "mmx")
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int n, m, S, T, Q;
struct Graph{
struct node{
int to, len, nxt;
} edge[200010 << 1];
int eid = 1, head[200010];
inline void add(int u, int v, int w = 0){
edge[++eid] = {v, w, head[u]};
head[u] = eid;
}
inline node & operator [] (const int x){
return edge[x];
}
} xym;
template <typename T>
using minHeap = priority_queue<T, vector<T>, greater<T>>;
int line[200010], whr[200010], tim;
bool inpath[200010];
struct Rebuild_Tree {
long long dis[200010];
int fr[200010], dpt[200010], bl[200010];
Graph yzh;
void dfs(int now, int anc) {
bl[now] = anc;
for (int i = yzh.head[now], to; to = yzh[i].to, i; i = yzh[i].nxt) {
dpt[to] = dpt[now] + 1;
dfs(to, inpath[to] ? to : anc);
}
}
void build(int S) {
minHeap<pair<long long, int>> Q;
memset(dis, 0x3f, sizeof (long long) * (n + 1));
Q.push({dis[S] = 0, S});
while (!Q.empty()) {
auto [ndis, now] = Q.top(); Q.pop();
if (ndis > dis[now]) continue;
for (int i = xym.head[now], to, len; to = xym[i].to, len = xym[i].len, i; i = xym[i].nxt) {
if (dis[to] > dis[now] + len) {
Q.push({dis[to] = dis[now] + len, to});
fr[to] = i ^ 1;
}
}
}
for (int i = 1; i <= n; ++i) if (i != S)
yzh.add(xym[fr[i]].to, i);
}
} S_tree, T_tree;
void getpath() {
for (int now = T; now; now = xym[S_tree.fr[now]].to) ++tim;
for (int now = T, cnt = 0; now; now = xym[S_tree.fr[now]].to, ++cnt)
line[tim - cnt] = now, whr[now] = tim - cnt, inpath[now] = true;
}
vector<pair<int, long long>> trans[200010];
struct President_Segment_Tree {
struct node {
int lson, rson;
long long val;
};
static node tree[200010 * 100];
static int tot;
static inline int copyNode(int idx) {
return tree[++tot] = idx ? tree[idx] : node {0, 0, 0x3f3f3f3f3f3f3f3f}, tot;
}
int root[200010];
void modify(int &idx, int l, int r, int p, long long v){
if (r < p || l > p) return;
idx = copyNode(idx), tree[idx].val = min(tree[idx].val, v);
if (l == r) return;
int mid = (l + r) >> 1;
modify(tree[idx].lson, l, mid, p, v);
modify(tree[idx].rson, mid + 1, r, p, v);
}
long long query(int idx, int trl, int trr, int l, int r) {
if (trl > r || trr < l || !idx) return 0x3f3f3f3f3f3f3f3f;
if (l <= trl && trr <= r) return tree[idx].val;
int mid = (trl + trr) >> 1;
return min(query(tree[idx].lson, trl, mid, l, r), query(tree[idx].rson, mid + 1, trr, l, r));
}
} tree;
President_Segment_Tree::node President_Segment_Tree::tree[200010 * 100];
int President_Segment_Tree::tot;
signed main() {
fread(buf, 1, MAX, stdin);
read(n), read(m);
for (int i = 1, u, v, w; i <= m; ++i) {
read(u), read(v), read(w);
xym.add(u, v, w);
xym.add(v, u, w);
}
read(S), read(T), S_tree.build(S), T_tree.build(T), getpath(), S_tree.dfs(S, S), T_tree.dfs(T, T);
for (int u = 1; u <= n; ++u) {
for (int i = xym.head[u], v, len; v = xym[i].to, len = xym[i].len, i; i = xym[i].nxt) {
if ((i ^ 1 ^ S_tree.fr[v]) && whr[T_tree.bl[v]] > whr[S_tree.bl[u]]) {
trans[whr[S_tree.bl[u]]].push_back({whr[T_tree.bl[v]], S_tree.dis[u] + len + T_tree.dis[v]});
}
}
}
for (int i = 1; i <= tim; ++i) {
tree.root[i] = tree.root[i - 1];
for (const auto& [to, len]: trans[i]) {
tree.modify(tree.root[i], 1, tim, to, len);
}
}
read(Q);
for (int i = 1, u, v; i <= Q; ++i) {
read(u), read(v);
if (S_tree.dpt[u] > S_tree.dpt[v]) swap(u, v);
if (xym[S_tree.fr[v]].to == u && inpath[v]) {
u = whr[u], v = whr[v];
long long res = tree.query(tree.root[u], 1, tim, v, tim);
if (res == 0x3f3f3f3f3f3f3f3f)
output_inf();
else
write(res);
putchar('\n');
} else {
if (S_tree.dis[T] == 0x3f3f3f3f3f3f3f3f)
output_inf();
else
write(S_tree.dis[T]);
putchar('\n');
}
}
fwrite(obuf, 1, o - obuf, stdout);
return 0;
}
标签:idx,int,题解,故乡,tree,200010,long,Violet,dis
From: https://www.cnblogs.com/XuYueming/p/18343974