P3387 SCC-1

· · 题解

经典的缩点模板
在图上dp，记忆化搜索总是比递推好用
学会了这个，就打下了缩点的基础
注意缩点时建出的新图不要犯变量混用的错误 

#include<bits/stdc++.h> 
using namespace std;
inline int read(){
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x;
}
struct Edge{
    int u,v,nxt;
}e[200010],a[200010];
int head[10010],cnt;
inline void add(int u,int v){
    e[++cnt].u=u;
    e[cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int head_[10010],cnt_;
inline void add_(int u,int v){
    a[++cnt_].u=u;
    a[cnt_].v=v;
    a[cnt_].nxt=head_[u];
    head_[u]=cnt_;
}
int point[10010],dfn[10010],low[10010],tim,s[10010],top,vis[10010];
int scc[10010],num,siz[10010];
int value[10010],f[10010];
void tarjan(int u){//板子 
    dfn[u]=low[u]=++tim;
    vis[u]=1;s[++top]=u;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].v;
        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]){
        ++num;
        while(1){
            int t=s[top--];
            vis[t]=0;scc[t]=num;
            value[num]+=point[t];//注意每个scc的点权要在此处更新,放到主函数会出错 
            if(t==u)break;
        }
    }
}
void dfs(int u){//记忆化搜索，不用反向建边 
    if(f[u])return;
    f[u]=value[u];
    int maxx=0;
    for(int i=head_[u];i;i=a[i].nxt){
        int v=a[i].v;
        if(!f[v])dfs(v);
        maxx=max(maxx,f[v]);
    }
    f[u]+=maxx;
}
int main(){
    int n,m;
    n=read();m=read();
    for(int i=1;i<=n;++i)point[i]=read();
    for(int i=1;i<=m;++i){
        int u,v;
        u=read();v=read();
        add(u,v);
    }
    for(int i=1;i<=n;++i)
        if(!dfn[i])
            tarjan(i);
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=m;++i){
        int u=e[i].u,v=e[i].v;
        if(scc[u]!=scc[v]) add_(scc[u],scc[v]);//建新图 
    }
    for(int i=1;i<=num;++i)
        if(!f[i])dfs(i);//求最长路 
    int ans=0;
    for(int i=1;i<=num;++i)
        ans=max(ans,f[i]);
    printf("%d",ans);
    return 0;
}