洛谷

洛谷题单指南-连通性问题-P3387 【模板】缩点

原题链接：https://www.luogu.com.cn/problem/P3387

题意解读：求一条路径，使路径经过的点权值之和最大，路径上点可以重复但每个点权值只算一次，输出最大的权值和。

解题思路：

1、问题分析

如果是DAG，可以直接通过拓扑排序来进行递推，计算到每个点的路径权值之和的最大值。

但是，如果图中存在环，则需要进行缩点处理，缩点的原理请参考：https://www.cnblogs.com/hackerchef/p/18851009

2、算法流程

计算所有强联通分量
完成缩点，缩点的权值是该强联通分量所有点权值之和
建立新图
在新图上跑一遍拓扑排序，然后递推出到每个点的路径权值之和的最大值
小技巧：对于Tarjan算法所得到的强联通分量，按照序号逆序天然具有拓扑序。

为什么？

这是因为拓扑排序除了用BFS，同样可以用DFS实现，具体实现逻辑是：

后序遍历：对图中每一个未访问过的节点进行DFS遍历，在递归返回时将节点加入结果列表
逆序输出：最终将后序遍历结果反转即得到拓扑排序
为什么这样可行？

DFS确保所有子孙节点先被处理
后序添加保证依赖关系被满足
反转后得到正确的依赖顺序
因此，直接逆序枚举所有强连通分量编号对应的缩点，再枚举缩点的所有邻边，进行递推更新即可。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 10005, M = 200005;
int h1[N], h2[N], e[M], ne[M], idx; //h1：原图 h2：缩点后的图
int dfn[N], low[N], timestamp;
stack<int> stk;
bool vis[N];
int scc[N], cnt;
int a[N]; //原图点权值
int sum[N]; //sum[i]表示强连通分量i中所有点权值之和
int f[N]; //f[i]表示以i为终点的路径上权值之和的最大值
int n, m;

void add(int h[], int a, int b)
{
    e[++idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;
    stk.push(u);
    vis[u] = true;

    for(int i = h1[u]; i; i = ne[i])
    {
        int v = e[i];
        if(!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(vis[v])
        {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if(low[u] == dfn[u])
    {
        cnt++;
        while(true)
        {
            int t = stk.top(); stk.pop();
            vis[t] = false;
            scc[t] = cnt;
            sum[cnt] += a[t]; //强联通分量内点的权值累加
            if(t == u) break;
        }
    }
}

void build()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = h1[i]; j; j = ne[j])
        {
            int u = scc[i], v = scc[e[j]];
            if(u != v)
                add(h2, u, v);
        }
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        add(h1, u, v);
    }

    //计算强联通分量
    for(int i = 1; i <= n; i++)
        if(!dfn[i])
            tarjan(i); 

    //缩点建图
    build(); 

    //递推求f[]
    for(int i = cnt; i >= 1; i--)
    {
        if(!f[i]) f[i] = sum[i]; //初始化
        for(int j = h2[i]; j; j = ne[j])
        {
            int v = e[j];
            if(f[v] < f[i] + sum[v])
            {
                f[v] = f[i] + sum[v];
            }
        }
    }

    //找最大值
    int ans = 0;
    for(int i = 1; i <= cnt; i++) ans = max(ans, f[i]);
    cout << ans;

    return 0;
}