题意简述
给定一张n个点m条边的无向图,满足m-n<=20,然后进行q次操作,每次给定两个点,询问两点间最短路。
数据范围:1<=n,m,q<=105。
算法概述
只看题面显然是个裸的全源最短路,但是再看数据范围……显然不是全源最短路。
所以这时候就需要发挥我们的聪明才智,在题目中找一些特殊性质或者发现一些结论之类的了。
显然,这道题最特殊的地方在于m-n<=20的限制,相当于在一棵树上多出了最多21条非树边。
对于给定的任意两个点a,b,最短路无非两种情况:
1.只经过树边,树上距离简单容斥一下,d[a]+d[b]-2*d[lca(a,b)];
2.经过非树边,那么我们可以枚举所有非树边,对于每条非树边(u,v,w),其构成的最短路有且仅有两种情况,其一是a→u→v→b,其二则是a→v→u→b,两者取min即可。
那么我们的算法框架就出来了:
先求一棵生成树(以下用Kruskal),然后把非树边处理出来。
先在树上做预处理,求出每个点到根的距离d。
把非树边加进去,然后对于所有在非树边上的点跑一遍最短路。
最后处理询问。
时间复杂度O(21*q+42*mlogn)。
参考代码
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; typedef long long ll; const int N=1e5+10; struct Edge{ int to,next,w; }edge[N<<1];int idx; int h[N]; void add_edge(int u,int v,int w){edge[++idx]={v,h[u],w};h[u]=idx;} struct E{ int u,v,w; bool operator <(const E &ed)const{ return w<ed.w; } }e[N],spc[N];int cnt; int fa[N]; ll dis[50][N]; int vis[N]; int n,m,q; int dep[N],son[N],siz[N]; int f[N],top[N]; ll d[N]; void dfs1(int p,int father) { f[p]=father; dep[p]=dep[father]+1; siz[p]=1; int max_son=0; for(int i=h[p];~i;i=edge[i].next) { int to=edge[i].to,w=edge[i].w; if(to==father)continue; d[to]=d[p]+w; dfs1(to,p); if(siz[to]>max_son)max_son=siz[to],son[p]=to; siz[p]+=siz[to]; } } void dfs2(int p,int t) { top[p]=t; if(!son[p])return; dfs2(son[p],t); for(int i=h[p];~i;i=edge[i].next) { int to=edge[i].to; if(to==f[p]||to==son[p])continue; dfs2(to,to); } } inline int lca(int x,int y) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]])swap(x,y); x=f[top[x]]; } return dep[x]<dep[y]?x:y; } int get(int x) { if(fa[x]==x)return fa[x]; return fa[x]=get(fa[x]); } void dijkstra(int s,ll dist[]) { memset(vis,0,sizeof vis); priority_queue<pair<ll,int> > q; q.push(make_pair(0,s)); dist[s]=0; while(!q.empty()) { int p=q.top().second; q.pop(); if(vis[p])continue; vis[p]=1; for(int i=h[p];~i;i=edge[i].next) { int to=edge[i].to,w=edge[i].w; if(dist[to]>dist[p]+w) { dist[to]=dist[p]+w; q.push(make_pair(-dist[to],to)); } } } } int main() { memset(h,-1,sizeof h); memset(dis,0x3f,sizeof dis); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); sort(e+1,e+m+1); for(int i=1;i<=m;i++) { int u=e[i].u,v=e[i].v,w=e[i].w; u=get(u),v=get(v); if(u==v) { spc[++cnt]=e[i]; continue; } fa[u]=v; add_edge(e[i].u,e[i].v,w); add_edge(e[i].v,e[i].u,w); } dfs1(1,0); dfs2(1,1); for(int i=1;i<=cnt;i++) { int u=spc[i].u,v=spc[i].v,w=spc[i].w; add_edge(u,v,w); add_edge(v,u,w); } for(int i=1;i<=cnt;i++) { int u=spc[i].u,v=spc[i].v; dijkstra(u,dis[(i<<1)-1]); dijkstra(v,dis[i<<1]); } scanf("%d",&q); while(q--) { int a,b;scanf("%d%d",&a,&b); ll ans=d[a]+d[b]-2*d[lca(a,b)]; for(int i=1;i<=cnt;i++) { int u=(i<<1)-1,v=i<<1,w=spc[i].w; ans=min(ans,dis[u][a]+dis[v][b]+w); ans=min(ans,dis[u][b]+dis[v][a]+w); } printf("%lld\n",ans); } return 0; }