P5236 【模板】静态仙人掌

(Updated: )
(7 mins to read)

每条边最多在一个简单环上的图每个环都是一个点双(方点),可以很方便的用圆方树来维护

求仙人掌图上两点间的最短路注意仙人掌上的圆方树的建法:每个简单环新建一个方点,环上每个点与方点连边,权值为到起点的最短距离,如果u是割点,向v连边权值为原图的边权(两个圆点连边)

做法

先建出圆方树考虑u和v在树上的LCA:

  • p为圆点,则答案就是树上两点的距离
  • p为方点,找出p的两个儿子a(u的祖先),b(v的祖先),a和b处在一个环上,答案是dis(a,b)+dis(a,u)+dis(b,v),注意dis(a,b)要取min
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 2e5 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
int dfn[N], low[N], clk, cnt, s[N], sum[N];
vector<pii> G[N], T[N];
int n, m, q;
constexpr int LOG = 16;
int fa[N][20], dep[N], dis[N];
void dfs(int u)
{
  for(int i=1; i<=LOG; i++)
    fa[u][i] = fa[fa[u][i-1]][i-1];
  for(auto it : T[u])
  {
    int v = it.fi, w = it.se;
    if(v==fa[u][0]) continue;
    dis[v] = dis[u] + w;
    dep[v] = dep[u] + 1;
    fa[v][0] = u;
    dfs(v);
  }
}
int LCA(int x,int y)
{
  if(dep[x]>dep[y]) swap(x,y);
  for(int i=LOG; i>=0; i--)
    if(dep[fa[y][i]]>=dep[x]) y = fa[y][i];
  if(x==y) return x;
  for(int i=LOG; i>=0; i--)
    if(fa[x][i]!=fa[y][i]) x = fa[x][i], y = fa[y][i];
  return fa[x][0];
}
void findcir(int u, int v, int w)
{
  ++cnt;
  int x = v, pre = w, pw = 0;
  while(x!=fa[u][0])
  {
    sum[x] = pre;
    pre += s[x];
    x = fa[x][0];
  }
  sum[cnt] = sum[u];
  sum[u] = 0;
  x = v;
  while(x!=fa[u][0])
  {
    pw = min(sum[x], sum[cnt]-sum[x]);
    T[cnt].pb({x, pw});
    T[x].pb({cnt, pw});
    x = fa[x][0];
  }
}
void tarjan(int u, int f)
{
  dfn[u] = low[u] = ++clk;
  for(auto it : G[u])
  {
    int v = it.fi, w = it.se;
    if(v==f) continue;
    if(!dfn[v])
    {
      fa[v][0] = u;
      s[v] = w;
      tarjan(v, u);
      low[u] = min(low[u], low[v]);
    }
    else low[u] = min(low[u], dfn[v]);
    if(low[v]>dfn[u])
    {
      T[u].pb({v, w});
      T[v].pb({u, w});
    }
  }
  for(auto it : G[u])
  {
    int v = it.fi, w = it.se;
    if(fa[v][0]==u||dfn[v]<=dfn[u]) continue;
    findcir(u, v, w);
  }
}
int find(int x, int y)
{
  int t = x;
  for(int i=LOG; i>=0; i--)
    if(dep[fa[fa[t][i]][0]]>=dep[y]) t = fa[t][i];
  return t;
}
int main()
{
  scanf("%d%d%d", &n, &m, &q);
  cnt = n;
  for(int i=1; i<=m; i++)
  {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    G[u].pb({v, w}); G[v].pb({u, w});
  }
  tarjan(1, 0);
  dep[1] = 1; dfs(1);
  while(q--)
  {
    int u, v;
    scanf("%d%d", &u, &v);
    int z = LCA(u, v);
    if(z<=n) printf("%d\n", dis[u]+dis[v]-2*dis[z]);
    else
    {
      int x = find(u, z), y = find(v, z);
      if(sum[x]>sum[y]) swap(x, y);
      int ans = dis[u]-dis[x]+dis[v]-dis[y]+min(sum[y]-sum[x], sum[x]+sum[z]-sum[y]);
      printf("%d\n", ans);
    }
  }
  return 0;
}