题解 P3387 【【模板】缩点】（待完善）
pantw
2018-01-25 22:55:32
QAQ还是先丢着吧emmm
回头再来写题解。
~~好久没有写操作符不空格的代码辣~~
----
```cpp
#include <cstdio>
#define maxn 10010
#define maxm 200010
int p[maxn],head[maxn],nhead[maxn],nxt[maxm],to[maxm],ec;
int stk[maxn],top,ins[maxn];
int dfn[maxn],low[maxn],ds;
int scc[maxn],sccno;
int in[maxn],res[maxn],ress,dp[maxn],val[maxn];
inline int min(int a,int b){
return a<b?a:b;
}
inline int max(int a,int b){
return a>b?a:b;
}
inline void add(int*h,int u, int v){
nxt[++ec]=h[u],h[u]=ec,to[ec]=v;
}
int dfs(int x){
if(dfn[x])return low[x];
dfn[x]=low[x]=++ds;
ins[x]=stk[++top]=x;
for(int e=head[x];e;e=nxt[e]){
if(!dfn[to[e]])low[x]=min(low[x],dfs(to[e]));
else if(ins[to[e]])low[x]=min(low[x],dfn[to[e]]);
}
if(dfn[x]==low[x]){
sccno++;
while(stk[top+1]!=x)scc[stk[top]]=sccno,ins[stk[top--]]=0;
}
return low[x];
}
void topo(int x){
res[++ress]=x;
for(int e=nhead[x];e;e=nxt[e])if(!--in[to[e]])topo(to[e]);
}
int main(){
int n,m,u,v,ans=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",p+i);
for(int i=1;i<=m;++i)scanf("%d%d",&u,&v),add(head,u,v);
for(int i=1;i<=n;++i)if(!dfn[i])dfs(i);
for(int i=1;i<=n;++i)for(int e=head[i];e;e=nxt[e])if(scc[i]!=scc[to[e]])add(nhead,scc[i],scc[to[e]]),in[scc[to[e]]]++;
for(int i=1;val[scc[i]]+=p[i],i<=sccno;++i)if(!in[i])topo(i);
for(int i=ress,x=res[i];i;ans=max(ans,dp[x]+=val[x]),x=res[--i])for(int e=nhead[x];e;e=nxt[e])dp[x]=max(dp[x],dp[to[e]]);
printf("%d\n", ans);
}
```