P3387 【模板】缩点

\(P3387\) 【模板】缩点

题目传送门

一、题目描述

给定一个 \(n\) 个点 \(m\) 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

输入格式
第一行两个正整数 \(n,m\)

第二行 \(n\) 个整数，其中第 \(i\) 个数 \(a_i\) 表示点 \(i\) 的点权。

第三至 \(m+2\) 行，每行两个整数 \(u,v\)，表示一条 \(u\rightarrow v\) 的有向边。

输出格式
共一行，最大的点权之和。

二、解题步骤

缩点，就是把一张有向有环图中的环缩成一个个点，形成一个有向无环图\(DAG\)。

首先我介绍一下为什么这题要缩点（有人肯定觉得这是放屁，这不就是缩点的模板题吗？但我们不能这么想，考试的时候不会有人告诉你打什么板上去吧）

根据题目意思，我们只 需要找出一条点权最大的路径 就行了，不限制点的个数。那么考虑对于一个环上的点被选择了，一整条环是不是应该都被选择，这一定很优，能选干嘛不选。很关键的是题目还允许我们重复经过某条边或者某个点，我们就不需要考虑其他了。因此整个环实际上可以看成一个点（选了其中一个点就应该选其他的点）

那么就正式开始缩环为点了。当然了，首先肯定是找环，使用\(tarjan\)算法进行缩点，求出一个\(DAG\)，并且，小修改一下，在合并为同一个强连通分量时，累加一下点权和，成为新的\(DAG\)图中点的权值。

在处理了环后，我们就重新建立一张图，以每个环为节点（孤立一个点也算也算环的，其实也就是强联通分量了）。在这张图中我们要\(dp\)，显然对于任意边\(<u,v>\),\(dp[v]=max(dp[v],dp[u]+p[v])\)，\(p[v]\)是\(v\)是这个环的总权值。

那么怎么解决无后效性问题呢？答案就是 拓扑排序 ,而 通过\(tarjan\)算法求出的新图，本身倒序枚举就是一个拓扑图，可以直接\(DP\)了

三、实现代码

#include <bits/stdc++.h>

using namespace std;
const int N = 100010, M = 2000010; // 因为要建新图，两倍的边
int n, m;                          // 点数、边数
int dfn[N], low[N], ts;
int stk[N], top, in_stk[N];
int id[N], scc_cnt, sz[N];
int f[N];
int h[N], hs[N], e[M], ne[M], idx; // h: 原图；hs: 新图
void add(int h[], int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int p[N]; //原图的点权
int q[N]; //新图的点权

// tarjan求强连通分量
void tarjan(int u) {
    dfn[u] = low[u] = ++ts;
    stk[++top] = u;
    in_stk[u] = true;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        } else if (in_stk[j])
            low[u] = min(low[u], dfn[j]);
    }
    if (dfn[u] == low[u]) {
        ++scc_cnt;
        int x;
        do {
            x = stk[top--];
            in_stk[x] = false;
            id[x] = scc_cnt;
            sz[scc_cnt]++;
            // scc_cnt:强连通块的编号
            q[scc_cnt] += p[x]; //叠加点权，生成连通块的总点权
        } while (x != u);
    }
}

int main() {
    memset(h, -1, sizeof h);   //原图
    memset(hs, -1, sizeof hs); //新图

    scanf("%d %d", &n, &m);
    //读入点权
    for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
    for (int i = 1; i <= m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        add(h, a, b);
    }
    //利用强连通分量，缩点，生成DAG
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i);

    // (2) 缩点，建图
    for (int u = 1; u <= n; u++)
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            int a = id[u], b = id[j];
            if (a != b)        //去重边
                add(hs, a, b); //加入到新图
        }

    // (3) 根据拓扑序遍历DAG，从scc_cnt向前遍历自然满足拓扑序
    for (int u = scc_cnt; u; u--) {
        // base case 递推起点
        if (!f[u]) f[u] = q[u];

        for (int i = hs[u]; ~i; i = ne[i]) {
            int j = e[i]; // 边(i, j)
            if (f[j] < f[u] + q[j]) f[j] = f[u] + q[j];
        }
    }

    // (4) 求解答案
    int res = 0;
    for (int i = 1; i <= scc_cnt; i++) res = max(res, f[i]);

    //输出
    printf("%d\n", res);
    return 0;
}

四、步骤与总结

• \(Tarjan\)强连通分量模板,扩展模板支持记录每个连通分量中点的个数，点权的叠加
• 重新建图,背诵邻接表支持多个的代码模板
• 全新建出来的图，倒序就是拓扑序，不用再做一次拓扑序，网上大部分代码有冗余的，无用
• \(DP\)类似三角不等式，更新最大点权和
• 枚举新图所有点，找出最大点权和