P3387 【模板】缩点 题解
传送门
1. 题意简述
模板题有什么题意简述……要求很清楚。
2. 思路分析
虽然题目很清晰简洁，但是思路没有那么直接。
1. 为什么要缩点？
因为题目写了是缩点的模板
如果遮掉最后一行，只看上面：
给定一个
那就是很模板很简单的拓扑排序，再套一个基础的 dp 即可。
但是还有一行：
允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。
诶？有向图里怎么会可以多次经过？唯一的可能就是有环。
那就麻烦了，因为拓扑必须要满足图是一个 DAG。
这时可以考虑缩点。
如果在一个环里，那么再环里走一圈绝对更优。所以完全可以把环（或者是 SCC）看成一个点！（感觉其实不是很好想的样子）
SCC 自然可以用 tarjan，tarjan 完缩点，缩点完正常拓扑 dp 即可。
3. 正确答案
接下来看代码：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e4 + 5, M = 1e5 + 5;
bool in_stk[N]; // 是否在栈里
stack <int> stk; // 记录一个 SCC 里的点
vector <int> g[N], g2[N]; // g 是初始的图，g2 是缩点之后的图
int n, m, cur, cnt, ans, x[M], y[M], a[N], dp[N], dfn[N], low[N], scc[N], ind[N], val[N];
// cur 用于在 tarjan 里面编时间戳，cnt 计算 SCC 数量，ans 是最后答案
// x 和 y 数组记录一条边的两个端点，dp[u] 指以 u 为结尾的最大值
// dfn 记录时间戳，low 记录能到达的最早的 dfn，scc 记录节点属于哪一个 SCC
// ind 记录拓扑里的入度，val 记录 SCC 里的值的和
void tarjan(int u)
{
dfn[u] = low[u] = ++cur; // 编号时间戳，开始的时候 low 是自己
stk.push(u); in_stk[u] = true; // 入栈，记录在栈里（相当于在 SCC 里）
for (int v : g[u]) // 遍历
{
if (!dfn[v]) // 如果没有记录过时间戳（没有到过）
{
tarjan(v); // 继续递归
low[u] = min(low[u], low[v]); // 更新维护 low
}
else if (in_stk[v]) low[u] = min(low[u], dfn[v]);
// 如果在 SCC 里，又遍历到了，代表有环（返祖边或者横插边）
// 用祖先的 dfn 来更新，但是不用递归了
// 事实上这里用 low[u] = min(low[u], low[v]) 也是没有问题的
// 但是在用 tarjan 计算割点的时候这样写会出锅，所以为了记忆方便，所以统一用 dfn 更新
}
if (dfn[u] == low[u]) // 发现能到的最早的点就是自己，显然这个 SCC 找完了
{
scc[u] = ++cnt; // 增加一个，并记录 u 属于 cnt 号 SCC
val[cnt] += a[u]; // 编号为 cnt 的 SCC 值的和加上 a[u]
in_stk[u] = false; // 最后会 pop 掉，这里先标记不在栈里（在最后写也完全没问题）
while (stk.top() != u) // 全部 pop
{
int now = stk.top(); stk.pop(); // 取出栈顶部
scc[now] = cnt; // 记录编号
val[cnt] += a[now]; // 加上值
in_stk[now] = false; // 标记
}
stk.pop(); // 记得 u 也要 pop
}
}
void topo()
{
queue <int> q;
for (int i = 1; i <= cnt; i++)
if (ind[i] == 0) q.push(i), dp[i] = val[i]; // 所有入度为 0 的入队，初始值为 val[i]
while (!q.empty())
{
int u = q.front(); q.pop(); // 取出队首
for (int v : g2[u]) // 遍历
{
ind[v]--; // 入度 -1
dp[v] = max(dp[v], dp[u] + val[v]); // 转移
if (ind[v] == 0) q.push(v); // 如果入度为 0，入队
}
}
}
signed main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= m; i++)
{
cin >> x[i] >> y[i];
g[x[i]].push_back(y[i]);
}
// 中规中矩的输入，x 和 y 记得存，之后要用
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i);
// 统计所有 SCC
for (int i = 1; i <= m; i++)
{
int xx = scc[x[i]], yy = scc[y[i]]; // 找到二者的 SCC
if (xx != yy) // 如果不一样才连边
{
ind[yy]++; // 增加入度
g2[xx].push_back(yy); // 连边
}
}
topo(); // 拓扑
for (int i = 1; i <= cnt; i++)
ans = max(ans, dp[i]); // 统计取最大值
cout << ans;
return 0;
}时间复杂度