P3387 【模板】缩点

Naffygo · 2019-07-05 10:28:41 · 个人记录

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<stack>
#include<queue>
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define N 10010
#define M 100010
using namespace std;

stack<int>sta;
queue<int>q;
struct node{
    int to,nxt,from;
}a[M],e[M];
int h[N],h2[N],w[N],dfn[N],low[N],vis[N],color[N],rd[N],dis[N];
int tot,deep,sum,n,m;

inline void add(int x,int y){
    a[++tot]=(node){y,h[x],x};
    h[x]=tot;
}

inline void add2(int x,int y){
    e[++sum]=(node){y,h2[x],x};
    h2[x]=sum;
}

inline void tarjan(int x){
    dfn[x]=low[x]=++deep;
    sta.push(x);vis[x]=1;
    for(int i=h[x];i;i=a[i].nxt){
        int p=a[i].to;
        if(!dfn[p]){
            tarjan(p);
            low[x]=min(low[x],low[p]);
        }
        else if(vis[p])low[x]=min(low[x],low[p]);
    }
    if(dfn[x]==low[x]){
        vis[x]=0;color[x]=x;
        int t=sta.top();
        while(t!=x){
            vis[t]=0;
            color[t]=x;
            w[x]+=w[t];
            sta.pop();
            t=sta.top();
        }
        sta.pop();
    }
}

inline void tuopu(){
    fr(i,1,n)
        if(color[i]==i && !rd[i])q.push(i),dis[i]=w[i];
    while(q.size()){
        int x=q.front();q.pop();
        for(int i=h2[x];i;i=e[i].nxt){
            int p=e[i].to;
            dis[p]=max(dis[p],dis[x]+w[p]);
            rd[p]--;
            if(rd[p]==0)q.push(p);
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    fr(i,1,n)
        scanf("%d",&w[i]);
    fr(i,1,m){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }
    fr(i,1,n)
        if(!dfn[i])tarjan(i);
    fr(i,1,m){
        int x=color[a[i].from],y=color[a[i].to];
        if(x!=y)add2(x,y),rd[y]++;
    }
    tuopu();
    int ans=0;
    fr(i,1,n)
        ans=max(ans,dis[i]);
    printf("%d",ans);
    return 0;
}