P3387
Aryper
·
·
个人记录
【模板】缩点
就是 SCC 缩点，缩完之后图是个 DAG，我们在 DAG 上做 DP 即可。
时间复杂度 O(n+m)。
突然发现自己的博客里好像没有关于 Tarjan 的具体讲解。这里简单提一嘴。
简单来说，给每个点两个信息，dfn 与 low。同时有一个栈来维护。
1. 点在栈中；
2. 存在一条从当前子树中出发的有向边，以该点为终点。
如果我们发现在从 $x$ 回溯之前，有 $dfn_x=low_x$ 说明是 SCC，从栈顶开始弹出直到 $x$ 也被弹出，这些点处于一个 SCC 中。
缩点什么的注意一下要枚举每个节点，再枚举每个节点出发的边。
代码：
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
const ll N=1e4,M=1e5;
ll n,m,u,v,tot,tc,cnt,top,num,ans,h;
ll ver[M*2+5],nxt[M*2+5],head[N+5];
ll vc[M*2+5],nc[M*2+5],hc[N+5];
ll stk[N+5],ins[N+5],c[N+5],dfn[N+5],low[N+5];
ll a[N+5],deg[N+5],val[N+5],f[N+5];
queue<ll> q;
void add_c(ll u,ll v) {
vc[++tc]=v;nc[tc]=hc[u];hc[u]=tc;
}
void tarjan(ll x) {
dfn[x]=low[x]=++num;
stk[++top]=x;ins[x]=1;
for(ll i=head[x];i;i=nxt[i]) {
if(!dfn[ver[i]]) {
tarjan(ver[i]);low[x]=min(low[x],low[ver[i]]);
}
else {
if(ins[ver[i]]) low[x]=min(low[x],dfn[ver[i]]);
}
}
if(dfn[x]==low[x]) {
cnt++;
do {
ins[stk[top]]=0;
c[stk[top]]=cnt;
val[cnt]+=a[stk[top]];
} while(x!=stk[top--]);
}
}
void add(ll u,ll v) {
ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;
}
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
return ret*f;
}
void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {
do{buf[++len]=x%10+48;x/=10;}while(x);
}
else {
putchar('-');
do{buf[++len]=-(x%10)+48;x/=10;}while(x);
}
while(len>=0) putchar(buf[len--]);
}
int main() {
n=read();m=read();
for(ll i=1;i<=n;i++) a[i]=read();
for(ll i=1;i<=m;i++) {
u=read();v=read();add(u,v);
}
for(ll i=1;i<=n;i++) {
if(!dfn[i]) tarjan(i);
}
for(ll x=1;x<=n;x++) {
for(ll i=head[x];i;i=nxt[i]) {
if(c[x]==c[ver[i]]) continue;
add_c(c[x],c[ver[i]]);
deg[c[ver[i]]]++;
}
}
for(ll i=1;i<=cnt;i++) {
if(!deg[i]) {q.push(i);f[i]=val[i];}
}
while(!q.empty()) {
h=q.front();q.pop();
for(ll i=hc[h];i;i=nc[i]) {
if(--deg[vc[i]]==0) q.push(vc[i]);
f[vc[i]]=max(f[vc[i]],f[h]+val[vc[i]]);
}
}
for(ll i=1;i<=cnt;i++) {
ans=max(ans,f[i]);
}
write(ans);
return 0;
}
```