P3387 缩点

缩点求DAG最长路

 
#include <bits/stdc++.h>
using namespace std ;
 const int N=1e4+2;
 int n,m,pool,a[N];
 int low[N],dfn[N];
 
 int kcnt,id[N];
 int f[N],val[N];
 
 vector<int> g[N],vc[N];
 stack<int> st;
 
 void tar(int x){
     dfn[x]=low[x]=++pool; st.push(x);
     int i,y;
     for(i=0;i<g[x].size();i++){
          y=g[x][i];
          if(!dfn[y]) tar(y),low[x]=min(low[x],low[y]);
          else if(!id[y]) low[x]=min(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]){
        kcnt++;
        do{
            y=st.top(); st.pop();
            id[y]=kcnt; 
        }while(y!=x);
    }
 }
 
int dp(int x){
       if(f[x]!=-1) return f[x]; f[x]=val[x];
       
       for(int i=0,y;i<vc[x].size();i++){
            y=vc[x][i]; 
            f[x]=max(f[x],val[x]+dp(y));
       }
       return f[x];
  }
 int main(){
     int i,j,x,y,t=0; 
      cin>>n>>m; 
      for(i=1;i<=n;i++) cin>>a[i];
      for(i=1;i<=m;i++) cin>>x>>y,g[x].push_back(y);
    
      for(i=1;i<=n;i++) if(!dfn[i]) tar(i);
      for(i=1;i<=n;i++) val[id[i]]+=a[i];
      
      for(i=1;i<=n;i++)
       for(j=0;j<g[i].size();j++){
             x=id[i],y=id[g[i][j]];
             if(x!=y) vc[x].push_back(y);
       }
    for(i=1;i<=kcnt;i++) f[i]=-1;
    for(i=1;i<=kcnt;i++) t=max(t,dp(i)); 
    cout<<t;
 }