BZOJ2125&3047 最短路(杨天)

2015.11.12 08:48 Thu| 20 visits oi_2016| 2016_刷题日常| Text

PoPoQQQ 大爷的题解完全看不懂。膜拜了 ydc 题解之后学到了杨天树的新姿势。

以下内容转自 ydc 题解

一点吐槽

最近学校在进行 NOIP 的模拟考试……本以为自己做 NOIP 的题还是可以的,然后遇到了这么一道题:

这里

说实话,遇到仙人掌图我心里就害怕。然后最近运气不错,要么考的是树,要么是树加一个环(NOI 快餐店),最不济也是多个不联通的环套树(ZJOI 骑士)。

众所周知,只有一个环的树只要随便删删边什么的就没了

省选集训把 HNOI 的勾股定理又考了一次,很可惜的是原题是还上爆枚的……而且省选集训考的那道还不用写独立集,偏偏要你求最大数据又很小……于是网络流秒之

虽然以前做过什么永无乡拉,仙人掌图的最大直径阿,但是对千古傻逼 ydc 而言那早已消散在历史的尘埃之中了

于是结果大家就知道了……ydc 跪倒在了联赛模拟题面前

题目来源

其实这不是原创题,原题在这里

感觉我总是被那些神爆了的前辈们给玩弄于股掌之间,比如 cdq 提到的独立插头阿,qzc 提到的动态最小生成树阿

果然我是雅礼最弱

题解

如果是树,经典做法是记录每个点到根的距离 dis(i),求 lca 然后 dis(a) + dis(b) − 2dis(lca) 即可。求 lca 经典做法是 tarjan 和倍增,个人深深的追随着伟大的倍增……tarjan 就只有很多年前在不会倍增的时候写过,深感难写 + 递归爆栈 + 各种挂链 + 尼玛还是离线,好恶心

事实上做仙人掌那部分数据的时候,用倍增肯定比用 tarjan 好写很多

如果是一个环,我们 DFS 出一棵生成树并把那条造成环的烦人非树边找到,之后可以分情况讨论:

  1. 环上的点可以通过删一条边变为链,然后记前缀和,并记录环长,通过前缀和一减得到链上距离,与环长减去这个距离的得到的值取 min 即可
  2. 不在环上,那么把环扔了,这个环套树就会变成一棵棵子树

    (a) 在同一棵子树的点我们求他们在生成树上的 lca 并用第一个做法做就是了

    (b) 不在一棵子树上的,可以让他们跑到环上去,通过求环上两点的距离,并记录他们跑上去的距离,然后就能得到答案了。实现的时候可以从环上的点开始 BFS 遍历子树

向上爬思路,在仙人掌图上几乎是不可以直接用的。不过转化为树然后 LCA 的方法却可以带来启发,因为仙人掌图还是有特殊性的,给人以明显的层次感

正常人都会想到缩环,但是仙人掌图的定义是每条边要么是桥要么只属于一个环,这意味着点可以属于多个环(比如一个菊花,由一个点向外不断扩展三角形样的子树)

杨天给了一种重新构图的方法:

对于题目给定的这么一个仙人掌图,我们直接做不好做,但是我们可以用如下方法构造出一棵“杨天树”:

  1. 任取一个点为根
  2. 对于桥边 (u,v),仍然保留
  3. 对于一个环,删去所有环边,让最高点向环上其他点连一条权值为 0 的边,把除了最高点以外的点都标记同一个颜色

等于是说,我们把原图直接给华丽的改造了

那么为什么要花这么多力气来改造呢?因为“杨天树”有性质

  1. 每个点要么没颜色,要么只会有一种颜色,即使出现了让我们直接缩环想法破灭了的共点环
  2. 将他们用倍增法不断往上跳,一直跳到 lca 的下面两个点,这时一个可以保证的结论是,在“杨天树”里,u −> lca(u,v) −> v 这条路径上,除了 lca(u,v) 以外的点一定会被走到。而且假设 u 往上跳跳到了 u',先 SPFA 跑出根到每个点的最短路后,dis(u,u') = dis(u,Root)−dis(u',Root)

这么一来,判断 u',v' 是否同色可以算出 dis(u',v'),再加上 dis(u,u'),dis(v,v') 的值即可

时间复杂度O(kE+qlogn),kE 指的是“队列优化的Bellman−Ford”(vfleaking 说过:“我拒绝使用 SPFA 一词”)

另一个可悲的故事是……考场上有 10% 的数据是 n,m ≤ 1000,q ≤ 10000,ydc 写若干次 SPFA, 骗到了小数据分,lyy 大神很认真的些 priority queue + Dijkstra, TLE 了……

以下内容并不转自其他人的题解

对于一个环,删去所有环边,让最高点向环上其他点连一条权值为这个点到最高点的距离的边,要不然最短路经过某一个环的时候,岂不是会直接把这个环上的权值当作 0 忽略掉?

最后判断是否同色的时候,如果它们都没有颜色或不同色,之间的距离就是各自到父亲的距离。

否则(按照我自己找环的方式)需要判断它们两个是否在环的最高点的两侧,再多加几个判断计算出它们在环上的距离。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <bits/stdc++.h>
using namespace std;

#define N 10005

int n, m, q, head[N], cnt, vis[N], deep[N], val[N], fa[N];
int col[N], road[N], root[N], len[N], dist[N], f[N][15], nowx, nowy;
stack<int> s;

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[N * 4];

inline void add(int x, int y, int z)
{
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

void color(int x, int y, int z)
{
    static int tot = 0; ++tot;
    int _x = x, _y = y;
    if (deep[x] < deep[y]) swap(x, y);
    while (deep[x] > deep[y])
        col[x] = tot, road[x] = 0, s.push(x), x = fa[x];
    while (x != y)
        col[x] = tot, road[x] = 0, s.push(x), x = fa[x],
        col[y] = tot, road[x] = 1, s.push(y), y = fa[y];
    root[tot] = x;
    while (!s.empty())
        dist[s.top()] = val[s.top()] - val[x], s.pop();
    len[tot] = dist[_x] + dist[_y] + z;
}

void dfs(int x)
{
    vis[x] = 1; deep[x] = deep[fa[x]] + 1;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].to != fa[x])
        {
            if (!vis[edge[i].to])
                fa[edge[i].to] = x,
                val[edge[i].to] = val[x] + edge[i].val,
                dfs(edge[i].to);
            else if (deep[edge[i].to] < deep[x])
                color(x, edge[i].to, edge[i].val);
        }
}

int lca(int x, int y)
{
    int flag;
    if (deep[x] < deep[y]) flag = 1, swap(x, y);
    else flag = 0;
    for (int i = 14; i >= 0; --i)
        if (deep[f[x][i]] >= deep[y])
            x = f[x][i];
    nowx = x; nowy = y;
    if (x == y) return x;
    for (int i = 14; i >= 0; --i)
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    nowx = x; nowy = y;
    if (flag) swap(nowx, nowy);
    return f[x][0];
}

int check(int x, int y)
{
    if (!col[x] || !col[y] || col[x] != col[y])
        return val[x] - val[fa[x]] + val[y] - val[fa[y]];
    else if (road[x] == road[y])
        return min(abs(dist[x] - dist[y]),
                    len[col[x]] - abs(dist[x] - dist[y]));
    else return min(dist[x] + dist[y],
                    len[col[x]] - (dist[x] + dist[y]));
}

int main()
{
    cin >> n >> m >> q;
    for (int x, y, z, i = 1; i <= m; ++i)
        scanf("%d%d%d", &x, &y, &z), add(x, y, z), add(y, x, z);
    dfs(1);
    memset(head, 0, sizeof head); cnt = 0;
    for (int i = 1; i <= n; ++i)
        if (col[i]) add(root[col[i]], i, min(dist[i], len[col[i]] - dist[i]));
        else add(fa[i], i, val[i] - val[fa[i]]);
    memset(vis, 0, sizeof vis);
    dfs(1);
    for (int i = 1; i <= n; ++i)
        f[i][0] = fa[i];
    for (int j = 1; j <= 14; ++j)
        for (int i = 1; i <= n; ++i)
            f[i][j] = f[f[i][j - 1]][j - 1];
    for (int x, y, i = 1; i <= q; ++i)
    {
        scanf("%d%d", &x, &y);
        int t = lca(x, y);
        if (nowx == nowy)
            printf("%d\n", val[x] - val[t] + val[y] - val[t]);
        else
            printf("%d\n", val[x] - val[nowx] + val[y] - val[nowy]
                            + check(nowx, nowy));
    }
    return 0;
}