给一个N个点M条边的连通无向图,满足每条边最多属于一个环,有Q组询问,每次询问两点之间的最短路径。
输入的第一行包含三个整数,分别表示N和M和Q 下接M行,每行三个整数v,u,w表示一条无向边v-u,长度为w 最后Q行,每行两个整数v,u表示一组询问
输出Q行,每行一个整数表示询问的答案
9 10 2
1 2 1
1 4 1
3 4 1
2 3 1
3 7 1
7 8 2
7 9 2
1 5 3
1 6 4
5 6 1
1 9
5 7
5
6
对于100%的数据,N<><>
对多源最短路问题,树上的经典做法是两点到根的距离减去两倍的 LCA 到根的距离,那么我们使用圆方树将仙人掌图转化为树后就可以按相同思路解决了。
然而我们发现原图的边权并没有很好地表现在我们建出来的圆方树上,所以我们首先解决边权问题:
找到换的根;
方点向环的根的连边的边权为 0 ;
环上其他点向方点连边,边权为到环的根的最短路径长度。
计算好边权后,对于两点的 LCA 是圆点的情况就可以直接按照树上的方法求距离了;而对于两点的 LCA 是方点的情况,其 LCA 是一个环,这两点一直向祖先走会到环上的两个不同位置,我们只需找到这两个位之间的到最短路。
具体方法:
Tarjan 找出所有的简单环,并记录环上信息备用,建圆方树;
这里需要注意,上一道题的图比仙人掌图还要特殊,每个节点一定属于一个环,因此我们可以对于每个节点只访问一次即可;可对于一般情况,我们在发现一个点 u 的下一个点 v 满足:
其实这里我们还有一种更好实现的处理方法:在 Tarjan 时维护一个边的栈,这样就可以免去许多细节处理问题。
2. 维护圆方树的倍增数组,记录每个点到根的距离。
3.倍增法求 LCA,若果 LCA 是环,还需要把两个点倍增到这个环上,在环上查询。
第一种实现 by PoPoQQQ
#include
#include
#include
#include
#include
#include
#define M 10100
#define INF 0x3f3f3f3f
using namespace std;
int n,m,q,cnt;
map
vector
int dis[M];
vector
int size[M];
map
void Add(int x,int y,int z)
{
if( f[x].find(y)==f[x].end() )
f[x][y]=INF;
f[x][y]=min(f[x][y],z);
}
namespace Cactus_Graph{
int fa[M<><>
pair
int Get_Depth(int x)
{
if(!fa[x][0]) dpt[x]=1;
if(dpt[x]) return dpt[x];
return dpt[x]=Get_Depth(fa[x][0])+1;
}
void Pretreatment()
{
int i,j;
for(j=1;j<>
{
for(i=1;i<>
fa[i][j]=fa[fa[i][j-1]][j-1];
for(i=n+1;i<><>
fa[i][j]=fa[fa[i][j-1]][j-1];
}
for(i=1;i<>
Get_Depth(i);
for(i=n+1;i<><>
Get_Depth(i);
}
int LCA(int x,int y)
{
int j;
if(dpt[x]<>
swap(x,y);
for(j=15;~j;j--)
if(dpt[fa[x][j]]>=dpt[y])
x=fa[x][j];
if(x==y) return x;
for(j=15;~j;j--)
if(fa[x][j]!=fa[y][j])
x=fa[x][j],y=fa[y][j];
second_lca=make_pair(x,y);
return fa[x][0];
}
}
void Tarjan(int x)
{
static int dpt[M],low[M],T;
static int stack[M],top;
map
dpt[x]=low[x]=++T;
stack[++top]=x;
for(it=f[x].begin();it!=f[x].end();it++)
{
if(dpt[it->first])
low[x]=min(low[x],dpt[it->first]);
else
{
Tarjan(it->first);
if(low[it->first]==dpt[x])
{
int t;
rings[++cnt].push_back(x);
belong[x].push_back(cnt);
Cactus_Graph::fa[cnt][0]=n+x;
do{
t=stack[top--];
rings[cnt].push_back(t);
Cactus_Graph::fa[n+t][0]=cnt;
}while(t!=it->first);
}
low[x]=min(low[x],low[it->first]);
}
}
}
void DFS(int x)
{
vector
static int stack[M];int i,j,top=0;
for(it=rings[x].begin();it!=rings[x].end();it++)
stack[++top]=*it;
stack[++top]=*rings[x].begin();
for(i=1;i<>
{
int p1=stack[i],p2=stack[i+1];
size[x]+=f[p1][p2];
if(i!=top-1)
dist[x][p2]=dist[x][p1]+f[p1][p2];
}
i=2;j=top-1;
while(i<>
{
if(dis[stack[i-1]]+f[stack[i-1]][stack[i]]<>
dis[stack[i]]=dis[stack[i-1]]+f[stack[i-1]][stack[i]],i++;
else
dis[stack[j]]=dis[stack[j+1]]+f[stack[j+1]][stack[j]],j--;
}
for(_it=rings[x].begin(),_it++;_it!=rings[x].end();_it++)
for(it=belong[*_it].begin();it!=belong[*_it].end();it++)
DFS(*it);
}
int main()
{
using namespace Cactus_Graph;
int i,x,y,z;
cin>>n>>m>>q;
for(i=1;i<>
{
scanf('%d%d%d',&x,&y,&z);
Add(x,y,z);Add(y,x,z);
}
Tarjan(1);
Pretreatment();
vector
for(it=belong[1].begin();it!=belong[1].end();it++)
DFS(*it);
for(i=1;i<>
{
scanf('%d%d',&x,&y);
int lca=LCA(n+x,n+y);
if(lca>n) printf('%d\n',dis[x]+dis[y]-2*dis[lca-n]);
else
{
int ans=dis[x]+dis[y]-dis[second_lca.first-n]-dis[second_lca.second-n];
int temp=abs(dist[lca][second_lca.first-n]-dist[lca][second_lca.second-n]);
ans+=min(temp,size[lca]-temp);
printf('%d\n',ans);
}
}
return 0;
}
第二种实现 by virgil
#include
#include
#include
#include
#include
#include
const int MAXN=1e4+5;
int N,M,Q;
int abs(int x){return (x<>
struct E{int next,to,val;} e[MAXN<3];int>
void addEdge(int u,int v,int w){e[++ecnt]=(E){G[u],v,w};G[u]=ecnt;}
void addEdge2(int u,int v,int w){addEdge(u,v,w);addEdge(v,u,w);}
void initCFS(){memset(G,0,sizeof(G));ecnt=0;}
struct A{int u,v,w;A(int u=0,int v=0,int w=0):u(u),v(v),w(w){};};
int dis[MAXN];bool inQ[MAXN];
std::queue
void SPFA(int S)
{
int i;
memset(dis,0x3f,sizeof(dis));
que.push(S);dis[S]=0;inQ[S]=true;
while(!que.empty())
{
int u=que.front();que.pop();
inQ[u]=false;
for(i=G[u];i;i=e[i].next)
{
int v=e[i].to;
if(dis[v]>dis[u]+e[i].val)
{
dis[v]=dis[u]+e[i].val;
if(!inQ[v]) que.push(v),inQ[v]=true;
}
}
}
}
std::stack st;
int belong[MAXN],ringRtDis[MAXN];
while(st.top().u!=u&&st.top().v!=v)
ringRtDis[a.u]=ringRtDis[a.v]+a.w;
if(a.u!=u) belong[a.u]=rcnt,anc[a.u][0]=u;
if(a.v!=u) belong[a.v]=rcnt,anc[a.v][0]=u;
ringRtDis[a.u]=ringRtDis[a.v]+a.w;
low[u]=std::min(low[u],low[v]);
anc[j][i]=anc[anc[j][i-1]][i-1];
int maxlogn=std::floor(std::log(N)/std::log(2));
if(belong[x]&&belong[x]==belong[y])
int xyDis=abs(ringRtDis[x]-ringRtDis[y]);
int minDis=std::min(xyDis,ringLen[belong[x]]-xyDis);
return xDis+yDis-dis[x]-dis[y]+minDis;
}else return xDis+yDis-2*dis[anc[x][0]];
联系客服