缩点求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; }
标签:缩点,int,st,P3387,dfn,low,pool From: https://www.cnblogs.com/towboa/p/16926685.html