40分求助

回复帖子

@Fee_cle6418 2018-11-09 09:38 回复

RT

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<stack>
#include<map>
#include<queue>
using namespace std;
struct Edge{
    int to,next;
}e[500005],e2[500005];
int n,m,cnt,cnt2,h[100005],h2[100005],sign,dis[100005];
int dfn[100005],low[100005],ins[100005],belong[100005],SCC,rd[100005],p[100005],p2[100005];
map<pair<int,int>,bool>qq;
stack<int>st;
queue<int>Q;
void Add_Edge(int u,int v){
    e[++cnt].to=v;
    e[cnt].next=h[u];
    h[u]=cnt;
}
void Add_Edge2(int u,int v){
    e2[++cnt2].to=v;
    e2[cnt2].next=h[u];
    h2[u]=cnt;
}
void Tarjan(int u){
    dfn[u]=low[u]=++sign;
    st.push(u);
    ins[u]=1;
    for(int i=h[u];i;i=e[i].next){
        if(!dfn[e[i].to]){
            Tarjan(e[i].to);
            low[u]=min(low[u],low[e[i].to]);
        }
        else if(ins[e[i].to]){
            low[u]=min(low[u],dfn[e[i].to]);
        }
    }
    if(low[u]==dfn[u]){
        SCC++;
        int t;
        do {
            t=st.top();
            st.pop();
            ins[t]=0;
            belong[t]=SCC;
            p2[SCC]+=p[t];
        } while(t!=u);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&p[i]);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        Add_Edge(x,y);
    }
    for(int i=1;i<=n;i++)if(!dfn[i])Tarjan(i);
    for(int i=1;i<=n;i++){
        for(int j=h[i];j;j=e[j].next){
            int q=e[j].to;
            if(belong[i]!=belong[q]&&!qq.count(make_pair(belong[i],belong[q])))Add_Edge2(belong[i],belong[q]),qq[make_pair(belong[i],belong[q])]=1,rd[belong[q]]++;
        }
    }
    for(int i=1;i<=SCC;i++){
        if(!rd[i])Q.push(i),dis[i]=p2[i];
    }
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        for(int i=h2[x];i;i=e2[i].next){
            int y=e2[i].to;
            dis[y]=max(dis[y],dis[x]+p2[y]);
            if(!(--rd[y]))Q.push(y);
        }
    }
    int ans=0;
    for(int i=1;i<=SCC;i++)ans=max(ans,dis[i]);
    cout<<ans<<endl;
    return 0;
}