题解：P3387 【模板】缩点

· · 题解

这篇题解适合对 Tarjan 算法已有大致了解但还不够熟悉，且面对此题毫无头绪的读者阅读，不太适合完全的初学者

深度思考部分

题意概括

有一张有向图，在上面寻找一条最长路，一个点的权值只计算一次。

算法分析

仔细读题就能发现，这个图有环，直接跑最长路会卡住，所以，我们要使用缩点。

缩点是什么？顾名思义，把有向图的多个点组成的环收缩成一个点的过程就是缩点。缩点结束后这个图就没环了，直接最长路就可以解决。

缩点怎么实现？Tarjan。

Tarjan

已经熟知 Tarjan 的可以跳过该部分。

Tarjan 算法可以找出图中所有强连通分量，即环，进而进行缩点，下面我来说说 Tarjan 到底是什么。

有一张有向图，从任意一顶点对它跑 DFS，不经过重复点，把遍历时经过的边构建成一棵树，我们称这棵树为 DFS 生成树。

DFS 生成树中的树边可以分为以下三种：

  1. 前向边 指向前遍历新节点产生的边；

  2. 返祖边 指遍历到头返回祖先的边；

  3. 横叉边 指在遍历过程中遍历到已经遍历过的点，且这个点不是它的祖先的边。

我们使用对它使用 Tarjan 遍历。

在遍历时，我们需要维护一个栈 st 与一个数组 inst 存储节点是否入栈。

我们设点 i 的 DFS 遍历的次序为 dfn_i，点 i 最早能通过返祖边回溯到的已经在栈中的节点的时间为 low_i。

每遍历到一个节点，就计算他的 dfn 和 low（显而易见，初始只能回溯到自己，所以 low_i=dfn_i），然后将此节点入栈。

接下来，依次遍历他的所有边，这会出现三种情况：

  1. 前向边 未遍历过的新节点（判断一下 dfn_i 是否有值），那么直接遍历该节点，该节点可以回溯目标节点，所以在遍历完成后还要更新当前节点的 low_i
  2. 返祖边 已经在栈中的节点（判断一下目标节点是否入栈 inst_i=true），那么该节点可以回溯目标节点，更新该节点的 low_i
  3. 横叉边 无意义，不做任何事情

在判断完所有边后，如果 dfn_i=low_i 那么这个结点就是一个强联通分量的起点（因为它最早被遍历，它的 dfn_i 和 low_i 值在这个联通分量中最小，不会被影响），栈中在这个节点上方的点与这个节点就可以组成连通分量，依次出栈，并对他们染色

这样进行 Tarjan 直到遍历结束，这样就可以找到图中所有的强连通分量，即环，并染色完毕。

缩点

在 Tarjan 染色完毕后，构建一张新图，把所有一个颜色的节点缩成一个节点，缩点结束后，这个图已经变成了一个有向无环图，接下来，最长路登场

最长路 拓扑排序

实现最长路可以使用 SPFA 或拓扑排序，因为 SPFA 在特殊情况下卡常，所以这里写的是拓扑排序。 拓扑排序也就不在过多赘述，只是注意一下拓扑的转移方程不要写错即可

代码部分

#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
#include <queue>

using namespace std;

const int N = 1e4 + 5;

// 变量定义
// val 点权 nval 新图点权
// dfn DFS序
// low 最早能通过返祖边回溯到的已经在栈中的节点时间
// color 颜色 scc 强连通分量个数
// 栈 st 存储正在遍历的节点 inst 节点是否入栈
// g 和 ng 原图和新图
// indu 入度
int n, m, val[N], s1, s2;
int dfn[N], low[N], inst[N], ti, dp[N];
int scc, color[N], nval[N], indu[N], maxn = 0;
vector<int> g[N], ng[N];
stack<int> st;

void tarjan(int x)
{
    // 计算 dfn 和 low
    dfn[x] = low[x] = ++ti;
    // 入栈
    st.push(x), inst[x] = 1;
    // 遍历所有的边
    for (auto y : g[x]) {
        if (!dfn[y]) {                     // 前向边
            tarjan(y);                     // 继续遍历
            low[x] = min(low[x], low[y]);  // 更新
        } else if (inst[y]) {              // 返祖边
            low[x] = min(low[x], dfn[y]);  // 更新
        }
    }
    // 是否为强连通分量起点
    if (dfn[x] == low[x]) {
        int y;
        scc++;  // 强联通分量个数++
        do {
            // 出栈
            y = st.top(), st.pop();
            inst[y] = 0;
            // 染色
            color[y] = scc;
            nval[scc] += val[y];
        } while (y != x);
        // 重复出栈直到栈中该节点上方的节点全部出完栈
    }
}

void topo()
{
    queue<int> q;

    for (int i = 1; i <= scc; i++) {  // 初始化
        if (!indu[i]) q.push(i), dp[i] = nval[i];
    }

    while (!q.empty()) {
        int x = q.front();
        maxn = max(maxn, dp[x]);
        q.pop();
        for (auto y : ng[x]) {
            dp[y] = max(dp[y], dp[x] + nval[y]);
            if (--indu[y] == 0) q.push(y);
        }
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &val[i]);

    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &s1, &s2);
        g[s1].push_back(s2);  // 建图
    }

    for (int i = 1; i <= n; i++) {  // Tarjan
        if (!dfn[i]) {
            tarjan(i);
        }
    }
    // 建新图
    for (int x = 1; x <= n; x++) {
        for (auto y : g[x]) {
            if (color[x] != color[y]) {  // 不属于同一个强连通分量
                ng[color[x]].push_back(color[y]);
                indu[color[y]]++;
            }
        }
    }
    // 拓扑算最短路
    topo();

    printf("%d", maxn);

    return 0;
}