CF757F Team Rocket Rises Again题解

· · 题解

小火箭嗖嗖嗖！

这道题是一道模板题，本来不想写的，但是闲得慌觉得很有价值就来试试水挑战一下，顺便帮我和大家复习了一遍支配树的知识点。

算法详解：

支配树是什么？什么是支配？对于一张有向图，确定一个根，如果根到节点 x 的每条路径都经过节点 y，那么称 y 是 x 支配点。求出原图的一个 dfs 树，那么 x 的支配点一定在 x 到根的链上。如果每个点向自己深度最深的支配点连边，就构成了支配树。

大致思路：

这道题我们先通过 Dijkstra 算法跑出最短路，然后就是运用深搜求出 dfs 树，同时，在求的过程中，要用 LCA 合并每一条链，并找出各个点的支配点，得到每个支配点的影响大小。最终，再用 ans 数组找出 siz 最大的支配点，得出结果。

具体步骤：

  1. 输入数据，记得由于题目中的图是带权无向图，那么就要建双向边。

  2. 老惯例，跑 dij 算法，求出每个点（不是一整条）的最短路路径，但要注意的是，再次放入队列中的 dis_i 值需要取负值（至于是为什么请读者自行思考），还有可以用优先队列优化时间复杂度。

  3. 接着，就是用 dfs 建树，由于把这个地方用 STL 中的队列太过复杂，所以本人建议用手写队列，更加方便。

  4. 这一步就比较关键了，由于一棵树是由很多条链组成的，因此我们就要用倍增 LCA 算法求出两个点的最近公共祖先，然后加以合并，并计算影响范围（也可以说叫大小）。

  5. 最终，我们用 ans 数组一一比较 siz_i 的大小，输出结果完结撒花。

代码如下：


#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5 + 10, T = 19;
priority_queue<pair<int, int> > q;
inline int read()
{
    register int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
struct node
{
    int to, next, val;
} edge[N * 2];
int n, m, s, tot, hed[N], dis[N], dep[N], v[N];
int head, tail, top[N], f[N][T + 1], siz[N];
void add(int x, int y, int z)
{
    edge[++tot].to = y;
    edge[tot].next = hed[x];
    edge[tot].val = z;
    hed[x] = tot;
    return;
}
void dij() // 垃圾的dij
{
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    q.push(make_pair(0, s));
    while (!q.empty())
    {
        int x = q.top().second;
        q.pop();
        if (v[x])
        {
            continue;
        }
        v[x] = 1;
        for (int i = hed[x]; i; i = edge[i].next)
        {
            int y = edge[i].to;
            if (dis[x] + edge[i].val < dis[y])
            {
                dis[y] = dis[x] + edge[i].val;
                q.push(make_pair(-dis[y], y)); // 这地方一定不能写错
            }
        }
    }
    return;
}
int LCA(int x, int y) // 垃圾的倍增LCA
{
    if (dep[x] > dep[y])
    {
        swap(x, y);
    }
    for (int i = T; i >= 0; i--)
    {
        if (dep[f[y][i]] >= dep[x])
        {
            y = f[y][i];
        }
    }
    if (x == y)
    {
        return x;
    }
    for (int i = T; i >= 0; i--)
    {
        if (f[x][i] != f[y][i])
        {
            x = f[x][i], y = f[y][i];
        }
    }
    return f[x][0];
}
void build()
{
    head = 1;
    tail = 1;
    top[1] = s;
    memset(v, 0, sizeof(v));
    for (int x = 1; x <= n; x++)
    {
        for (int i = hed[x]; i; i = edge[i].next)
        {
            int y = edge[i].to;
            int val = edge[i].val;
            if (dis[x] + edge[i].val == dis[edge[i].to])
            {
                v[edge[i].to]++;
            }
        }
    }
    while (head <= tail) // 模拟队列
    {
        int x = top[head++];
        dep[x] = dep[f[x][0]] + 1;
        for (int i = 1; i <= T; i++)
        {
            f[x][i] = f[f[x][i - 1]][i - 1];
        }
        for (int i = hed[x]; i; i = edge[i].next)
        {
            int y = edge[i].to;
            if (dis[x] + edge[i].val != dis[y])
            {
                continue;
            }
            v[y]--;
            if (!f[y][0])
            {
                f[y][0] = x;
            }
            else
            {
                f[y][0] = LCA(f[y][0], x);
            }
            if (!v[y])
            {
                top[++tail] = y;
            }
        }
    }
    return;
}
signed main()
{
    n = read();
    m = read();
    s = read();
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        u = read();
        v = read();
        w = read();
        add(u, v, w);
        add(v, u, w);//建带权无向图一定是双向的，要存双向边
    }
    dij();
    build();
    int ans = 0;
    for (int i = tail; i > 1; i--)
    {
        siz[top[i]]++, siz[f[top[i]][0]] += siz[top[i]];
        ans = max(ans, siz[top[i]]);
    }
    cout << ans;
    return 0;
}

AC记录