BZOJ2125 最短路

BZOJ

Luogu

分析

先建出圆方树。圆圆边的边权就为树上的边权,方圆边的边权为圆点到方点父节点的最短路。

考虑树上最短路是怎么做的。求出 $\mathrm{lca}$ ,然后答案是 $dis[u]+dis[v]-dis[lca]*2$ ,这里的 $dis$ 是到根的距离。

那么圆方树上是一样的,只是要分类讨论一下。

如果 $\mathrm{lca}$ 是圆点,那么和树上是一样的。

如果 $\mathrm{lca}$ 是方点,那么要求出 $\mathrm{lca}$ 的两个儿子 $A$ 和 $B$ ,分别是 $u$ 和 $v$ 的祖先。然后答案就是 $dis[u]-dis[A]+dis[v]-dis[B]+\mathrm{dist}(A,B)$ 。这里的 $\mathrm{dist}(A,B)$ 直接两种情况取 $\min$ 就好了。

现在考虑怎么求这个儿子。如果这个儿子是轻儿子,那么它是一条重链的顶端,直接跳重链就好了;如果是重儿子,那么跳重链会跳过 $\mathrm{lca}$ 。

具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=20000+10,M=100000+10;

//图
struct Graph {
    struct edge { int v,w,nxt; } e[M];
    int head[N];
    
    inline void addEdge(int u,int v,int w) {
        static int cnt=0;
        e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
    }
} G,T;

//变量
int n,m,Q,tot=0;
int dfn[N],low[N],tim=0;
int fa[N],hson[N],top[N],sz[N],dep[N];
int sum[N],dis[N],pre[N];

//LCA
inline int getLCA(int u,int v) {
    int tu=top[u],tv=top[v];
    while (tu!=tv) {
        if (dep[tu]<dep[tv]) swap(u,v),swap(tu,tv);
        u=fa[tu],tu=top[u];
    }
    return dep[u]<dep[v]?u:v;
}

//跳到儿子上
inline int find(int u,int f) {
    int ans;
    while (top[u]!=top[f]) ans=top[u],u=fa[top[u]];
    return u==f?ans:hson[f];
}

//树剖
inline void dfs1(int u,int pa) {
    fa[u]=pa,dep[u]=dep[pa]+1,sz[u]=1;
    for (re int i=T.head[u];i;i=T.e[i].nxt) {
        int v=T.e[i].v,w=T.e[i].w; if (v==pa) continue;
        dis[v]=dis[u]+w; dfs1(v,u); sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson[u]=v;
    }
}
inline void dfs2(int u,int anc) {
    top[u]=anc;
    if (hson[u]) dfs2(hson[u],anc);
    for (re int i=T.head[u];i;i=T.e[i].nxt) {
        int v=T.e[i].v;
        if (v!=fa[u]&&v!=hson[u]) dfs2(v,v);
    }
}

//建方点
inline void build(int u,int v,int w) {
    for (re int i=v,s=w;i!=fa[u];i=fa[i]) sum[i]=s,s+=pre[i];
    sum[++tot]=sum[u],sum[u]=0;
    for (re int i=v;i!=fa[u];i=fa[i]) {
        int d=min(sum[i],sum[tot]-sum[i]);
        T.addEdge(tot,i,d),T.addEdge(i,tot,d);
    }
}

//tarjan
inline void tarjan(int u,int pa) {
    dfn[u]=low[u]=++tim;
    for (re int i=G.head[u];i;i=G.e[i].nxt) {
        int v=G.e[i].v,w=G.e[i].w; if (v==pa) continue;
        if (!dfn[v]) fa[v]=u,pre[v]=w,tarjan(v,u),low[u]=min(low[u],low[v]);
        else low[u]=min(low[u],dfn[v]);
        if (low[v]>dfn[u]) T.addEdge(u,v,w),T.addEdge(v,u,w);
    }
    for (re int i=G.head[u];i;i=G.e[i].nxt) {
        int v=G.e[i].v,w=G.e[i].w;
        if (fa[v]!=u&&dfn[u]<dfn[v]) build(u,v,w);
    }
}

int main() {
    tot=n=read(),m=read(),Q=read();
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read(),w=read();
        G.addEdge(u,v,w),G.addEdge(v,u,w);
    }
    tarjan(1,0),dfs1(1,0),dfs2(1,1);
    while (Q--) {
        int u=read(),v=read(),t=getLCA(u,v);
        if (t<=n) printf("%d\n",dis[u]+dis[v]-(dis[t]<<1));
        else {
            int A=find(u,t),B=find(v,t);
            if (sum[A]<sum[B]) swap(A,B);
            printf("%d\n",dis[u]-dis[A]+dis[v]-dis[B]
                         +min(sum[A]-sum[B],sum[t]+sum[B]-sum[A]));
        }
    }
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 34 PM

4 条评论

  1. Siyuan

    大聚聚 $\color{black}{\text{M}}\color{red}{\text{_sea}}$ 暴打仙人掌 %%%

    1. M_sea
      @Siyuan

      小姐姐快女装!

  2. xgzc

    大聚聚M_sea暴打仙人掌%%%

    1. M_sea
      @xgzc

      大聚聚xgzc AK APIO %%%

发表评论