大型网站开发 赚钱,在线设计签名免费网站,施工企业组织目标,安宁网站建设 熊掌号题意#xff1a;仙人掌图最短路。 算法#xff1a;圆方树DP#xff0c;$O(n\log nQ\log n)$ 首先建出仙人掌圆方树#xff08;与点双圆方树的区别在于直接连割边#xff0c;也就是存在圆圆边#xff09;#xff0c;然后考虑点u-v的最短路径#xff0c;显然就是#xf…题意仙人掌图最短路。 算法圆方树DP$O(n\log nQ\log n)$ 首先建出仙人掌圆方树与点双圆方树的区别在于直接连割边也就是存在圆圆边然后考虑点u-v的最短路径显然就是在圆方树上u-v的路径上的所有边权之和加上每个环方点中连出去的两个点的最短距离。 现在问题就是如何求出环上两个点的最短路径。考虑这样设定边权首先显然圆圆边的边权就是原图的边权然后设一个环在搜索树中深度最小的点为这个环的根则方圆边的边权是环的根到这个点的最短距离这个可以在Tarjan的时候直接求出。 但是圆方树问题通常需要在LCA处分圆方点讨论。首先如果LCA是圆点那么直接做即可。如果是方点就需要决定要不要走环的另一侧这个同样直接讨论即可。 具体见代码感觉思路还是比较清晰的。 1 #includecstdio2 #includealgorithm3 #define rep(i,l,r) for (int il; ir; i)4 using namespace std;5 6 const int N20010;7 int n,m,Q,u,v,w,tot,tim,top,dep[N],len[N],type[N],stk[N];8 int dfn[N],low[N],dis[N],lst[N],fa[N][16],sm[N][16];9
10 struct E{
11 int cnt,h[N],to[N1],nxt[N1],val[N1];
12 void add(int u,int v,int w){ to[cnt]v; val[cnt]w; nxt[cnt]h[u]; h[u]cnt; }
13 }G,G1;
14
15 void work(int x,int k){
16 tot; int t; len[tot]dis[stk[top]]-dis[x]lst[stk[top]];
17 do{
18 tstk[top--];
19 int Adis[t]-dis[x],Blen[tot]-A;
20 G1.add(tot,t,min(A,B)); type[t](AB);
21 }while (t!k);
22 G1.add(x,tot,0);
23 }
24
25 void Tarjan(int x,int pre){
26 //printf(%d\n,x);
27 dfn[x]low[x]tim; stk[top]x;
28 for (int iG.h[x],k; i; iG.nxt[i]){
29 if ((kG.to[i])pre) continue;
30 if (!dfn[k]){
31 dis[k]dis[x]G.val[i]; Tarjan(k,x);
32 //printf(%d %d %d %d\n,x,k,dfn[x],low[k]);
33 if (low[k]dfn[x]) top--,G1.add(x,k,G.val[i]);
34 else if (low[k]dfn[x]) work(x,k);
35 low[x]min(low[x],low[k]);
36 }else low[x]min(low[x],dfn[k]),lst[x]G.val[i];
37 }
38 }
39
40 void dfs(int x,int pre){
41 for (int iG1.h[x],k; i; iG1.nxt[i])
42 fa[kG1.to[i]][0]x,dep[k]dep[x]1,sm[k][0]G1.val[i],dfs(k,x);
43 }
44
45 int lca(int u,int v){
46 if (dep[u]dep[v]) swap(u,v);
47 int tdep[u]-dep[v],res0;
48 for (int i15; ~i; i--) if (t(1i)) ressm[u][i],ufa[u][i];
49 if (uv) return res;
50 for (int i15; ~i; i--) if (fa[u][i]!fa[v][i])
51 ressm[u][i]sm[v][i],ufa[u][i],vfa[v][i];
52 if (fa[u][0]n) return sm[u][0]sm[v][0]res;
53 int Asm[u][0],Bsm[v][0],mn;
54 if (type[u]type[v]) mnmin(abs(A-B),len[fa[u][0]]-abs(A-B));
55 else mnmin(AB,len[fa[u][0]]-A-B);
56 return resmn;
57 }
58
59 int main(){
60 freopen(bzoj2125.in,r,stdin);
61 freopen(bzoj2125.out,w,stdout);
62 scanf(%d%d%d,n,m,Q); totn;
63 rep(i,1,m) scanf(%d%d%d,u,v,w),G.add(u,v,w),G.add(v,u,w);
64 Tarjan(1,0); dfs(1,0);
65 //rep(i,1,tot) printf(%d ,low[i]); puts();
66 rep(j,1,15) rep(i,1,tot)
67 fa[i][j]fa[fa[i][j-1]][j-1],sm[i][j]sm[i][j-1]sm[fa[i][j-1]][j-1];
68 rep(i,1,Q) scanf(%d%d,u,v),printf(%d\n,lca(u,v));
69 return 0;
70 } 转载于:https://www.cnblogs.com/HocRiser/p/9143979.html
