BZOJ2125: 最短路 仙人掌+LCA

题目大意：

给定一个仙人掌图，多次询问两点之间的最短路。

数据范围$n,q\leq{10000}$。

题解：

首先我们发现$m\leq{2n-2}$。

这是怎么来的呢？

首先找到一颗生成树，有$n-1$条边。

接下来有一些非树边，它们覆盖的树边显然不能有交，否则就会出现一条边出现在多个环上的情况了。

因此边最多的情况是每条非树边恰好覆盖一条树边，此时有$n-1$条非树边。

其次考虑仙人掌的结构。

对于仙人掌求出点双连通分量，其中每个点双要么是一个二元环，要么是一条边，要么是一个多元环。

其中割点会属于多个点双连通分量。

一个割点会将所有它属于的点双连通分量连通。

尝试将仙人掌有根化，则每个点双都有一个根节点即为深度最小的节点。

定义一个点的所在点双表示这个点属于的所有点双中根节点深度最小的点双。

我们考虑通过一次DFS来构建点双形成的树结构：

为了方便起见，我们找一个非割点作为整棵仙人掌的根，这样的节点显然是存在的。

对于一个点双$x$，我们考虑其中除了根节点之外的所有割点所属的除了这个点双本身的之外的点双$y$，并将$y$作为$x$在树结构上的儿子DFS下去。

对于根节点所在的点双之外的点双$y$，每个点双都存在一个父亲点双$x$，且点双$y$的根节点是连接点双$x,y$的割点。

现在需要求最短路，考虑两个点可以怎么走到一起。

考虑一个点$x$，首先从$x$走到$x$所在点双的根节点$y$，再从$y$走到$y$所在点双的根节点$z$，这样不断向上走，直到两个点走到同一个点双。

我们不妨重建一棵树，树中节点$x$的父亲是$x$所在点双的根节点，父亲边的权值为两个点之间在环上的最短路。

这样的话，对于询问的两个点$x,y$：

如果其中一个$y$是另一个$x$的祖先，那么说明深度较大$x$的那个不断向上爬，直到$x$的父亲是$y$，然后再走一步。

否则我们倍增爬到两者的父亲相同，判断两者此时的关系：

如果两者所在点双相同，直接调用两个节点之间的环上最短路；

否则说明两个点所在点双不同，向上却爬到了相同的点双根节点，直接分别将答案加上两个点到点双根节点的最短路就行了。

于是我们还不知道，怎么求一个点双（其实就是一个环）上两点的最短路呢？

我们对一个点记录其DFS树上的父亲以及父亲边的长度，再对一个点记录最后一次返祖回到这个点的节点以及返祖边的长度。

这个只要在Tarjan过程中顺便记录就行了。

当我们找到一个点双的时候（即满足$low[v]\geq{dfn[u]}$时），证明我们一定找到了一个割点，同时在栈中最后连续的一段再加上这个点就形成了这个点双（环）。在环上维护一下关于某个点的单向距离，再算出环的总长度，然后就能两种方向取个最小值了。

就说这么多吧，具体看代码。

如果觉得我的算法太污可以去看大爷的算法。

代码：

#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int getc() {
    static const int L = 1 << 15;
    static char buf[L], *S = buf, *T = buf;
    if (S == T) {
        T = (S = buf) + fread(buf, 1, L, stdin);
        if (S == T)
            return EOF;
    }
    return *S++;
}
int getint() {
    int c;
    while (!isdigit(c = getc()));
    int x = c - '0';
    while (isdigit(c = getc()))
        x = (x << 1) + (x << 3) + c - '0';
    return x;
}
#define N 10010
#define M 20010
int n, m, q;
int head[N], nxt[M << 1], to[M << 1], w[M << 1];
void addedge(int a, int b, int c) {
    static int q = 1;
    to[q] = b;
    w[q] = c;
    nxt[q] = head[a];
    head[a] = q++;
}
void make(int a, int b, int c) {
    addedge(a, b, c);
    addedge(b, a, c);
}
int dfn[N], low[N], tclock, stack[N], top;
int pedge[N], pa[N], backedge[N], backnode[N];
int cnt;
vector<int> node[N];
vector<int> bel[N];
int len[N];
map<int, int> dis[N];
int abs(int x) {
    return x < 0 ? -x : x;
}
int calcDis(int id, int x, int y) {
    static int dx, dy;
    dx = dis[id][x];
    dy = dis[id][y];
    return min(abs(dx - dy), len[id] - abs(dx - dy));
}
void Tarjan(int x, int fa_edge) {
    static int y, total;
    dfn[x] = low[x] = ++tclock;
    stack[++top] = x;
    for (int j = head[x]; j; j = nxt[j]) {
        if (!dfn[to[j]]) {
            pedge[to[j]] = w[j];
            pa[to[j]] = x;
            Tarjan(to[j], (j + 1) >> 1);
            low[x] = min(low[x], low[to[j]]);
            
            if (low[to[j]] >= dfn[x]) {
                ++cnt;
                total = 0;
                while (1) {
                    y = stack[top--];
                    bel[y].push_back(cnt);
                    node[cnt].push_back(y);
                    dis[cnt][y] = total;
                    total += pedge[y];
                    if (y == to[j])
                        break;
                }
                bel[x].push_back(cnt);
                node[cnt].push_back(x);
                if (node[cnt].size() == 2) {
                    dis[cnt][x] = total;
                    len[cnt] = total + (backnode[x] == y ? backedge[x] : pedge[y]);
                }
                else {
                    dis[cnt][x] = total;
                    len[cnt] = total + backedge[x];
                }
            }
        }
        else if ((j + 1) / 2 != fa_edge) {
            low[x] = min(low[x], dfn[to[j]]);
            backedge[to[j]] = w[j];
            backnode[to[j]] = x;
        }
    }
}
int root[N], paid[N], Root;
struct Tree {
    int head[N], nxt[N], to[N], w[N], pa[N][14], dis[N][14], dep[N];
    void addedge(int a, int b, int c) {
        static int q = 1;
        to[q] = b;
        w[q] = c;
        nxt[q] = head[a];
        head[a] = q++;
    }
    void dfs(int x) {
        for (int j = head[x]; j; j = nxt[j]) {
            pa[to[j]][0] = x;
            dis[to[j]][0] = w[j];
            dep[to[j]] = dep[x] + 1;
            dfs(to[j]);
        }
    }
    void init() {
        dep[Root] = 1;
        dfs(Root);
        for (int j = 1; j <= 13; ++j)
            for (int i = 1; i <= n; ++i) {
                pa[i][j] = pa[pa[i][j - 1]][j - 1];
                dis[i][j] = dis[i][j - 1] + dis[pa[i][j - 1]][j - 1];
            }
    }
    int query(int x, int y) {
        int i, j, ans = 0;
        if (dep[x] < dep[y])
            swap(x, y);
        if (x == y)
            return 0;
        if (dep[x] != dep[y]) {
            for (i = 13; i >= 0; --i)
                if (dep[pa[x][i]] > dep[y]) {
                    ans += dis[x][i];
                    x = pa[x][i];
                }
            if (pa[x][0] == y)
                return ans + calcDis(paid[x], x, y);
            for (i = 13; i >= 0; --i)
                if (dep[pa[x][i]] >= dep[y]) {
                    ans += dis[x][i];
                    x = pa[x][i];
                }
        }
        for (i = 13; i >= 0; --i)
            if (pa[x][i] != pa[y][i]) {
                ans += dis[x][i];
                ans += dis[y][i];
                x = pa[x][i];
                y = pa[y][i];
            }
        if (paid[x] == paid[y])
            return ans + calcDis(paid[x], x, y);
        else
        //  return ans + calcDis(paid[x], x, pa[x][0]) + calcDis(paid[y], y, pa[y][0]);
            return ans + dis[x][0] + dis[y][0];
    }
}myTree;
void dfs(int id, int x) {
    int i, j;
    for (int i = 0; i < node[id].size(); ++i) {
        if (node[id][i] != x) {
            root[node[id][i]] = x;
            paid[node[id][i]] = id;
            myTree.addedge(x, node[id][i], calcDis(id, x, node[id][i]));
            for (int j = 0; j < bel[node[id][i]].size(); ++j)
                if (bel[node[id][i]][j] != id)
                    dfs(bel[node[id][i]][j], node[id][i]);
        }
        
    }
}
int main() {
    //freopen("tt.in", "r", stdin);
    //freopen("me.out", "w", stdout);
    n = getint(), m = getint(), q = getint();
    int i, j, a, b, c;
    while (m--) {
        a = getint(), b = getint(), c = getint();
        if (a == b)
            continue;
        make(a, b, c);
    }
    
    Tarjan(1, -1);
    //printf("%d\n", calcDis(1, 1, 5));
    for (i = 1; i <= n; ++i) {
        if (bel[i].size() == 1) {
            Root = i;
            root[i] = i;
            paid[i] = bel[i][0];
            dfs(bel[i][0], i);
            break;
        }
    }
    myTree.init();
    
    while (q--) {
        a = getint();
        b = getint();
        printf("%d\n", myTree.query(a, b));
    }
    
    return 0;
}