[BZOJ2125]最短路Description給一個(gè)N個(gè)點(diǎn)M條邊的連通無(wú)向圖，滿(mǎn)足每條邊最多屬于一個(gè)環(huán)，有Q組詢(xún)問(wèn)，每次詢(xún)問(wèn)兩點(diǎn)之間的最短路徑。 Input輸入的第一行包含三個(gè)整數(shù)，分別表示N和M和Q 下接M行，每行三個(gè)整數(shù)v，u，w表示一條無(wú)向邊v-u，長(zhǎng)度為w 最后Q行，每行兩個(gè)整數(shù)v，u表示一組詢(xún)問(wèn) Output輸出Q行，每行一個(gè)整數(shù)表示詢(xún)問(wèn)的答案 Sample Input9 10 2 Sample Output5 HINT對(duì)于100%的數(shù)據(jù)，N<><> 對(duì)多源最短路問(wèn)題，樹(shù)上的經(jīng)典做法是兩點(diǎn)到根的距離減去兩倍的 LCA 到根的距離，那么我們使用圓方樹(shù)將仙人掌圖轉(zhuǎn)化為樹(shù)后就可以按相同思路解決了。 然而我們發(fā)現(xiàn)原圖的邊權(quán)并沒(méi)有很好地表現(xiàn)在我們建出來(lái)的圓方樹(shù)上，所以我們首先解決邊權(quán)問(wèn)題：
計(jì)算好邊權(quán)后，對(duì)于兩點(diǎn)的 LCA 是圓點(diǎn)的情況就可以直接按照樹(shù)上的方法求距離了；而對(duì)于兩點(diǎn)的 LCA 是方點(diǎn)的情況，其 LCA 是一個(gè)環(huán)，這兩點(diǎn)一直向祖先走會(huì)到環(huán)上的兩個(gè)不同位置，我們只需找到這兩個(gè)位之間的到最短路。 具體方法：
2. 維護(hù)圓方樹(shù)的倍增數(shù)組，記錄每個(gè)點(diǎn)到根的距離。 3.倍增法求 LCA，若果 LCA 是環(huán)，還需要把兩個(gè)點(diǎn)倍增到這個(gè)環(huán)上，在環(huán)上查詢(xún)。 第一種實(shí)現(xiàn) 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; } 第二種實(shí)現(xiàn) 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]]; |
|
|
來(lái)自： 長(zhǎng)沙7喜 > 《信息課》
