[BZOJ2125]最短路(圓方樹DP)

題意：仙人掌圖最短路。

算法：圓方樹DP，$O(n\log n+Q\log n)$

首先建出仙人掌圓方樹（與點雙圓方樹的區別在于直接連割邊，也就是存在圓圓邊），然后考慮點u-v的最短路徑，顯然就是：在圓方樹上u-v的路徑上的所有邊權之和，加上每個環（方點）中連出去的兩個點的最短距離。

現在問題就是：如何求出環上兩個點的最短路徑。考慮這樣設定邊權，首先顯然圓圓邊的邊權就是原圖的邊權，然后設一個環在搜索樹中深度最小的點為這個環的根，則方圓邊的邊權是環的根到這個點的最短距離，這個可以在Tarjan的時候直接求出。

但是圓方樹問題通常需要在LCA處分圓方點討論。首先如果LCA是圓點，那么直接做即可。如果是方點，就需要決定要不要走環的另一側，這個同樣直接討論即可。

具體見代碼，感覺思路還是比較清晰的。

#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=l; i<=r; i++)
using namespace std;

const int N=20010;
int n,m,Q,u,v,w,tot,tim,top,dep[N],len[N],type[N],stk[N];
int dfn[N],low[N],dis[N],lst[N],fa[N][16],sm[N][16];

struct E{
    int cnt,h[N],to[N<<1],nxt[N<<1],val[N<<1];
    void add(int u,int v,int w){ to[++cnt]=v; val[cnt]=w; nxt[cnt]=h[u]; h[u]=cnt; }
}G,G1;

void work(int x,int k){
    tot++; int t; len[tot]=dis[stk[top]]-dis[x]+lst[stk[top]];
    do{
        t=stk[top--];
        int A=dis[t]-dis[x],B=len[tot]-A;
        G1.add(tot,t,min(A,B)); type[t]=(A<=B);
    }while (t!=k);
    G1.add(x,tot,0);
}

void Tarjan(int x,int pre){
    //printf("%d\n",x);
    dfn[x]=low[x]=++tim; stk[++top]=x;
    for (int i=G.h[x],k; i; i=G.nxt[i]){
        if ((k=G.to[i])==pre) continue;
        if (!dfn[k]){
            dis[k]=dis[x]+G.val[i]; Tarjan(k,x);
            //printf("%d %d %d %d\n",x,k,dfn[x],low[k]);
            if (low[k]>dfn[x]) top--,G1.add(x,k,G.val[i]);
            else if (low[k]==dfn[x]) work(x,k);
            low[x]=min(low[x],low[k]);
        }else low[x]=min(low[x],dfn[k]),lst[x]=G.val[i];
    }
}

void dfs(int x,int pre){
    for (int i=G1.h[x],k; i; i=G1.nxt[i])
        fa[k=G1.to[i]][0]=x,dep[k]=dep[x]+1,sm[k][0]=G1.val[i],dfs(k,x);
}

int lca(int u,int v){
    if (dep[u]<dep[v]) swap(u,v);
    int t=dep[u]-dep[v],res=0;
    for (int i=15; ~i; i--) if (t&(1<<i)) res+=sm[u][i],u=fa[u][i];
    if (u==v) return res;
    for (int i=15; ~i; i--) if (fa[u][i]!=fa[v][i])
        res+=sm[u][i]+sm[v][i],u=fa[u][i],v=fa[v][i];
    if (fa[u][0]<=n) return sm[u][0]+sm[v][0]+res;
    int A=sm[u][0],B=sm[v][0],mn;
    if (type[u]==type[v]) mn=min(abs(A-B),len[fa[u][0]]-abs(A-B));
        else mn=min(A+B,len[fa[u][0]]-A-B);
    return res+mn;
}

int main(){
    freopen("bzoj2125.in","r",stdin);
    freopen("bzoj2125.out","w",stdout);
    scanf("%d%d%d",&n,&m,&Q); tot=n;
    rep(i,1,m) scanf("%d%d%d",&u,&v,&w),G.add(u,v,w),G.add(v,u,w);
    Tarjan(1,0); dfs(1,0);
    //rep(i,1,tot) printf("%d ",low[i]); puts("");
    rep(j,1,15) rep(i,1,tot)
        fa[i][j]=fa[fa[i][j-1]][j-1],sm[i][j]=sm[i][j-1]+sm[fa[i][j-1]][j-1];
    rep(i,1,Q) scanf("%d%d",&u,&v),printf("%d\n",lca(u,v));
    return 0;
}

?