题目描述
为了随时与rainbow快速交流,Freda制造了两部传呼机。Freda和rainbow所在的地方有N座房屋、M 条双向光缆。
每条光缆连接两座房屋,传呼机发出的信号只能沿着光缆传递,并且传呼机的信号从光缆的其中一端传递到另一端需要花费t单位时间。
现在Freda要进行Q次试验,每次选取两座房屋,并想知道传呼机的信号在这两座房屋之间传递至少需要多长时间。
N座房屋通过光缆一定是连通的,并且这M条光缆有以下三类连接情况:
A:光缆不形成环,也就是光缆仅有N-1 条。
B:光缆只形成一个环,也就是光缆仅有N 条。
C:每条光缆仅在一个环中。
请你帮帮他们。
输入样例
5 4 2
1 2 1
1 3 1
2 4 1
2 5 1
3 5
2 1
输出样例
3
1
算法
静态仙人掌(圆方树)
为了不遗漏的刷完算法进阶,蒟蒻特地去学习了圆方树算法
圆方树算法是近年的热点,还是有必要了解下
前置知识: 运用Tarjan求点双联通分量
由于实现细节比较复杂,蒟蒻这里就不在赘述,代码中有详细注释
学习时参见的博客: https://www.luogu.org/blog/PinkRabbit/Introduction-to-Round-Square-Tree
时间复杂度分析:$\Theta(n + q\log n)$
C++ 代码
//为了不遗漏的刷完算法进阶,蒟蒻特地去学习了圆方树算法
//圆方树算法是近年的热点,还是有必要了解下
//ID: LRL52 Date: 2019.8.26
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#include<bits/stdc++.h>
using namespace std;
const int N = 20055, M = 20055; char ss[1 << 21], *A = ss, *B = ss, cc;
inline char gc(){return A == B && (B = (A = ss) + fread(ss, 1, 1 << 21, stdin), A == B) ? EOF : *A++;}
template<class T>inline void rd(T &x){
int f = 1; x = 0, cc = gc(); while(cc < '0' || cc > '9'){if(cc == '-') f = -1; cc = gc();}
while(cc >= '0' && cc <= '9'){x = (x << 3) + (x << 1) + (cc ^ 48); cc = gc();} x *= f;
}
int n, m, q, ct, ct2, ext;
int head[N], head2[N], sum[N], b[N], fa[N], dep[N], son[N], Top[N];
int dis[N];
struct edge{
int v, nxt, w;
}e[M << 1], e2[M << 1];
inline void adde(int from, int to, int w){
e[++ct].v = to;
e[ct].w = w;
e[ct].nxt = head[from];
head[from] = ct;
}
inline void adde2(int from, int to, int w){
e2[++ct2].v = to;
e2[ct2].w = w;
e2[ct2].nxt = head2[from];
head2[from] = ct2;
}
struct Tarjan{
int clk, dfn[N], low[N], fa[N];
void solve(int u, int v, int w){
int pre = w, i = v;
while(i != fa[u]){
sum[i] = pre;
pre += b[i];
i = fa[i];
}
sum[++ext] = sum[u], sum[u] = 0; //环上权值存到方点上,u为圆点,v为方点时边权为0
i = v; int mw = 0;
while(i != fa[u]){
mw = min(sum[i], sum[ext] - sum[i]);
adde2(ext, i, mw);
adde2(i, ext, mw);
i = fa[i];
}
}
void tarjan(int x, int far){ //这里的tarjan略有不同
dfn[x] = low[x] = ++clk;
for(int i = head[x]; i; i = e[i].nxt){
int v = e[i].v;
if(v == far) continue;
if(!dfn[v]){
fa[v] = x, b[v] = e[i].w;
tarjan(v, x);
low[x] = min(low[x], low[v]);
}
else low[x] = min(low[x], dfn[v]);
if(low[v] <= dfn[x]) continue; //圆点之间连接长度原长的边
adde2(x, v, e[i].w);
adde2(v, x, e[i].w);
}
for(int i = head[x]; i; i = e[i].nxt){
int v = e[i].v;
if(fa[v] == x || dfn[v] <= dfn[x]) continue;
solve(x, v, e[i].w); //找到非树边,然后连边
}
}
}T;
int dfs(int x, int depth){
dep[x] = depth, Top[x] = x; int tson = 0, maxs = 0, size = 1;
for(int i = head2[x]; i; i = e2[i].nxt){
int v = e2[i].v;
if(v == fa[x]) continue;
fa[v] = x; dis[v] = dis[x] + e2[i].w;
int dx = dfs(v, depth + 1);
size += dx;
if(dx > maxs){
maxs = dx;
tson = v;
}
}
if(tson) Top[tson] = x, son[x] = tson;
return size;
}
int findtop(int x){return Top[x] == x ? x : Top[x] = findtop(Top[x]);}
int LCA(int x, int y){
while(findtop(x) != findtop(y)){
if(dep[Top[x]] < dep[Top[y]]) swap(x, y);
x = fa[Top[x]];
}
return dep[x] < dep[y] ? x : y;
}
int findson(int x, int lca){
int pre = 0;
while(findtop(x) != findtop(lca)){
pre = Top[x]; //上一个节点应该记录重链顶端的点!!
x = fa[Top[x]];
}
return x == lca ? pre : son[lca];
}
int main(){
freopen("CH6402.in", "r", stdin);
//freopen("CH6402.out", "w", stdout);
rd(n), rd(m), rd(q); int x, y, z;
rep(i, 1, m){
rd(x), rd(y), rd(z);
adde(x, y, z), adde(y, x, z);
}
ext = n;
T.tarjan(1, -1);
dfs(1, 0);
int ans = 0;
rep(i, 1, q){
rd(x), rd(y);
int lca = LCA(x, y);
if(lca <= n) ans = dis[x] + dis[y] - 2 * dis[lca];
else{
int s1 = findson(x, lca), s2 = findson(y, lca);
ans = dis[x] + dis[y] - dis[s1] - dis[s2];
if(sum[s1] < sum[s2]) swap(s1, s2);
ans += min(sum[s1] - sum[s2], sum[lca] - sum[s1] + sum[s2]);
}
printf("%d\n", ans);
}
return 0;
}
写得太好啦!!!