BZOJ | Luogu

https://cmxrynp.github.io/2018/10/29/BZOJ-2125-%E6%9C%80%E7%9F%AD%E8%B7%AF/

https://blog.csdn.net/LPA20020220/article/details/88887231

## 题意

给你一个有 n 个点和 m 条边的仙人掌图，和 q 组询问，

每次询问两个点之间的最短路。

## 题解

### 圆方树

const int N = int(2e4) + 9, LV = 15; VII adj[N], adjj[N]; int dfn[N], low[N], tt, sta[N], top; int fa[LV][N], dep[N], D[N], DD[N], L[N]; int n, nn; inline int move_up(int x, int t){ for (int lv=0;t;++lv,t>>=1) if (t&1) x = fa[lv][x]; return x; } inline int lca(int x, int y) { if (dep[x]>dep[y]) swap(x,y); y=move_up(y, dep[y]-dep[x]); if (x==y) return x; DWN(lv, LV, 0) if (fa[lv][x]!=fa[lv][y]) x = fa[lv][x], y = fa[lv][y]; return fa[0][x]; } void getLCA(int x, int y, int &a, int &b, int &z) { if (dep[x]>dep[y]) swap(x,y); y=move_up(y, dep[y]-dep[x]); if (x==y) {z = x; return;} DWN(lv, LV, 0) if (fa[lv][x]!=fa[lv][y]) x = fa[lv][x], y = fa[lv][y]; a = x; b = y; z = fa[0][x]; } void add_edge(int u, int v, LL w) { adjj[u].PB(MP(v, w)); } #define v it->fi #define w it->se void tarjan(int u = 1, int p = -1) { low[u] = dfn[u] = ++tt; sta[++top] = u; ECH(it, adj[u]) if (v != p) { if (!dfn[v]) { D[v] = D[u] + w; tarjan(v, u); checkMin(low[u], low[v]); if (dfn[v] == low[v]) add_edge(u, v, w); // tree edge } else if (dfn[v] < dfn[u]) { // find circle checkMin(low[u], dfn[v]); add_edge(v, ++nn, 0); L[nn] = D[u]-D[v]+w; for (int i=top;sta[i]!=v;--i) { int d = D[sta[i]]-D[v]; add_edge(nn, sta[i], min(d, L[nn]-d)); } } } --top; } #define p fa[0][u] void dfs(int u = 1) { ECH(it, adjj[u]) { dep[v] = dep[u] + 1; DD[v] = DD[u] + w; fa[0][v] = u; for (int lv=0;fa[lv+1][v]=fa[lv][fa[lv][v]];++lv); dfs(v); } } #undef p #undef w #undef v int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif int Q, m; RD(n, m, Q); DO(m) { int x, y, w; RD(x, y, w); adj[x].PB(MP(y, w)); adj[y].PB(MP(x, w)); } nn = n; tarjan(); dfs(); DO(Q) { int x, y, a, b, z; RD(x, y); getLCA(x, y, a, b, z); //cout << x << " " << y << " " << z<< endl; if (z <= n) { // round one ... OT(DD[x]+DD[y]-DD[z]*2); } else { // square one ... int d = abs(D[a]-D[b]); OT(DD[x]+DD[y]-DD[a]-DD[b]+min(d, L[z]-d)); } } }