假如题目名称不是“【模板】缩点”的话，是否能想到缩点？
这道题如何联想到缩点？
首先题目给出的图，可能存在强连通分量，这样的强连通分量中，所有的点权都可全部取到，所以如果走到分量之中的一个点，那么整个分量的点权都可以加上，且题目说点权非负了。这样缩点之后优化了空间时间，也避免了在连通分量中重复兜圈。
那么进行tarjan算法缩点。这里称每个强连通分量为团。每个团上存储的是团内点权之和。缩点后重新建图，创立新的邻接表。每个团的权都是非负，这里就利用到了DAG的性质是无环的（废话），所以对其进行拓扑排序，进行基本的dp，将最大值递推下去即可。
这里总结一下一般的缩点题型的特征：
- 强连通分量
- 数据大多在点上
- 点不可以重复，边可以重复
- 与之后的DAG有关
- ……
#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
vector<int>e[N];
vector<int>ne[N];
stack<int>stk;
queue<int>q;
bitset<N>instk;
int dfn[N], low[N], tot;
int scc[N], siz[N], scc_sum[N], cnt;
int deg_in[N], deg_out[N];
int w[N];
int dp[N];
int n, m;
void tarjan(int u)
{
dfn[u] = low[u] = ++ tot;
stk.push(u);
instk[u]= 1;
for (int v : e[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[v], low[u]);
} else if (instk[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
int v;
++cnt;
do {
v = stk.top();
stk.pop();
instk[v] = 0;
scc[v] = cnt;
scc_sum[cnt] += w[v];
} while (v != u);
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &w[i]);
}
for (int i = 1, a, b; i <= m; i++) {
scanf("%d%d", &a, &b);
e[a].push_back(b);
}
for (int i = 1; i <= n; i++) {
if (!dfn[i]) {
tarjan(i);
}
}
for (int i = 1; i <= n; i++) {
for (int v : e[i]) {
if (scc[i] != scc[v]) {
ne[scc[i]].push_back(scc[v]);
deg_in[scc[v]] ++;
deg_out[scc[i]] ++;
}
}
}
for (int i = 1; i <= cnt; i++) {
if (deg_in[i] == 0) {
q.push(i);
dp[i] = scc_sum[i];
}
}
while (q.size()) {
int u = q.front();
q.pop();
for (int v : ne[u]) {
dp[v] = max(dp[v], dp[u] + scc_sum[v]);
deg_in[v] --;
if (deg_in[v] == 0)
q.push(v);
}
}
int ans = 0;
for (int i = 1; i <= cnt; i++) {
ans = max(ans, dp[i]);
}
printf("%d\n", ans);
return 0;
}