迷宫花坛(garden)

本文主要是介绍迷宫花坛(garden)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

圣玛格丽特学园的一角有一个巨大、如迷宫般的花坛。大约有一个人这么高的大型花坛，做成迷宫的形状，深受中世纪贵族的喜爱。维多利加的小屋就坐落在这迷宫花坛的深处。某一天早晨，久城同学要穿过这巨大的迷宫花坛，去探望感冒的维多利加。

整个迷宫可以用N个路口与M条连接两个不同路口的无向通道来描述。路口被标号为1到N，每条通道有各自的长度。整个迷宫一定是连通的，迷宫中可能存在若干个环路，但是，出于美观考虑，每个路口最多只会属于一个简单环路。例如，图1所示的迷宫是非常美观的，但图2则不符合我们的描述，因为3号路口同属于两个简单环。

你需要回答多个这样的询问：假如久城处在路口x，维多利加的小屋处在路口y，久城最短需要走多少距离才能到达小屋？

输入

第一行2个整数N,M，表示迷宫花坛的路口数和通道数；

接下来N行，每行3个整数x,y,z，描述一条连接路口x与路口y，长度为z的通道；

再接下来1行包含一个整数Q，表示询问数量；

之后Q行，每行2个整数x,y，描述一个询问。
输出

对于每个询问输出一行一个整数，表示最短距离。
输入样例

4 4
1 2 1
2 3 2
1 3 2
3 4 1
2
2 4
1 3
输出样例

3
2
说明

对于30%的数据，N≤100；

另有30%的数据，保证N=M；

对于100%的数据，1≤N≤100,000，Q≤200,000，1≤x,y≤N，1≤z≤1000.

.
.
.
.
.
.
分析
主要分成 lca 在环上和不在环上，先缩环(环上的点直接连向最高点)，那么不在环上的 lca 就跟在树上一样求法；
在环上的话就先求出环外部分，再计算环内距离；
所以一遍 spfa 求从根出发的最短路，再一遍 dfs 求 dfs 序的 dis ，用来处理环上距离，然后 bfs 计算深度用来倍增求 lca，然后分类求答案即可；
注意边数就是点的4倍，还要算上缩环时连的边。

.
.
.
.
.
.
90分程序：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;int n,m,Q,head[1000005],cnt=1,dis[1000005],dist[1000005],tj,col[1000005],tot,dfn[1000005];
int fa[1000005],len[1000005],f[100005][20],dep[1000005];
bool del[4000005],vis[1000005];queue<int>q;struct edge
{int to,next,w;
}a[4000005];inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;
}void add(int x,int y,int z)
{a[++cnt].to=y;a[cnt].next=head[x];a[cnt].w=z;head[x]=cnt;
}int check(int x)
{return x<0?-x:x;
}void spfa()
{memset(dist,0x3f,sizeof(dist));memset(vis,0,sizeof(vis));dist[1]=0;q.push(1);vis[1]=1;while (q.size()){int x=q.front();q.pop();vis[x]=0;for (int i=head[x];i;i=a[i].next){int u=a[i].to;if (dist[u]>dist[x]+a[i].w){dist[u]=dist[x]+a[i].w;if (!vis[u]){vis[u]=1;q.push(u);}}}}
}void make(int x,int e)
{int i,y=x;x=a[e].to;len[++tj]+=a[e].w;col[y]=tj;del[e]=del[e^1]=1;add(x,y,0);add(y,x,0);for (i=fa[y];(y=a[i^1].to)!=x;i=fa[y]){len[tj]+=a[i].w;col[y]=tj;del[i]=del[i^1]=1;add(x,y,0);add(y,x,0);}col[x]=tj;len[tj]+=a[i].w;
}void dfs(int x)
{dfn[x]=++tot;for (int i=head[x];i;i=a[i].next){int u=a[i].to;if (!dfn[u]){fa[u]=i;dis[u]=dis[x]+a[i].w;dfs(u);} elseif (dfn[u]<dfn[x]&&fa[x]!=(i^1)) make(x,i);}
}void bfs()
{while (q.size()) q.pop();memset(vis,0,sizeof(vis));vis[1]=1;q.push(1);dep[1]=1;while (q.size()){int x=q.front();q.pop();for (int i=head[x];i;i=a[i].next){int u=a[i].to;if (vis[u]||del[i]) continue;vis[u]=1;dep[u]=dep[x]+1;f[u][0]=x;for (int j=1;j<=15;j++)f[u][j]=f[f[u][j-1]][j-1];q.push(u);}}
}int lca(int x,int y)
{if (dep[x]<dep[y]) swap(x,y);int a=x,b=y,k=dep[x]-dep[y];for (int i=0;i<=15;i++)if (k&(1<<i)) x=f[x][i];if (x==y) return dist[a]-dist[b];for (int i=15;i>=0;i--)if (f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}if (col[x]&&col[x]==col[y]){int l=check(dis[x]-dis[y]);return dist[a]-dist[x]+dist[b]-dist[y]+min(l,len[col[x]]-l); }return dist[a]+dist[b]-2*dist[f[x][0]];
}int main()
{n=read();m=read();for (int i=1;i<=m;i++){int x,y,z;x=read();y=read();z=read();add(x,y,z);add(y,x,z);}spfa();dfs(1);bfs();scanf("%d",&Q);for (int i=1;i<=Q;i++){int x,y;x=read();y=read();printf("%d\n",lca(x,y));}return 0;
}

这篇关于迷宫花坛(garden)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---