1 #include <algorithm>  2 #include <cstring>  3 #include <cstdio>  4 #include <queue>  5   6 using namespace std;  7   8 const int M(150000+5);  9 const int N(30000+15); 10 int n,m,u,v,val[N],ans; 11  12 int hed[N],had[N],sumedge; 13 struct Edge 14 { 15     int v,next; 16 }edge[M]; 17 void ins(int u,int v,int *head) 18 { 19     sumedge++; 20     edge[sumedge].v=v; 21     edge[sumedge].next=head[u]; 22     head[u]=sumedge; 23 } 24  25 int dfn[N],low[N],tim; 26 int col[N],sumcol,cval[N]; 27 int Stack[N],instack[N],top; 28 void DFS(int now) 29 { 30     dfn[now]=low[now]=++tim; 31     Stack[++top]=now,instack[now]=1; 32     for(int i=hed[now];i;i=edge[i].next) 33     { 34         int to=edge[i].v; 35         if(!dfn[to]) DFS(to),low[now]=min(low[now],low[to]); 36         else if(instack[to]) low[now]=min(low[now],dfn[to]); 37     } 38     if(low[now]==dfn[now]) 39     { 40         col[now]=++sumcol; 41         cval[sumcol]+=val[now]; 42         for(;Stack[top]!=now;top--) 43         { 44             col[Stack[top]]=sumcol; 45             cval[sumcol]+=val[Stack[top]]; 46             instack[Stack[top]]=0; 47         } 48         instack[now]=0;top--; 49     } 50 } 51  52 int rd[N]; 53 void Get_map() 54 { 55     for(u=1;u<=n;u++) 56         for(int i=hed[u];i;i=edge[i].next) 57         { 58               v=edge[i].v; 59               if(col[u]!=col[v]) 60               rd[col[v]]++,ins(col[u],col[v],had); 61         } 62 } 63  64 queue<int>que; 65 int inq[N],dis[N]; 66 int SPFA(int s) 67 { 68     int ret=dis[s]=cval[s]; 69     memset(inq,0,sizeof(inq)); 70     que.push(s);inq[s]=1; 71     while(!que.empty()) 72     { 73         u=que.front();que.pop(),inq[u]=0; 74         for(int i=had[u];i;i=edge[i].next) 75         { 76             v=edge[i].v; 77             if(dis[v]<dis[u]+cval[v]) 78             { 79                 dis[v]=dis[u]+cval[v]; 80                 ret=max(ret,dis[v]); 81                 if(!inq[v]) 82                     que.push(v),inq[v]=1; 83             } 84         } 85     } 86     return ret; 87 } 88  89 void init() 90 { 91     sumcol=sumedge=top=tim=ans=0; 92     memset(rd,0,sizeof(rd)); 93     memset(hed,0,sizeof(hed)); 94     memset(had,0,sizeof(had)); 95     memset(dis,0,sizeof(dis)); 96     memset(col,0,sizeof(col)); 97     memset(dfn,0,sizeof(dfn)); 98     memset(low,0,sizeof(low)); 99     memset(val,0,sizeof(val));100     memset(cval,0,sizeof(cval));101     memset(Stack,0,sizeof(Stack));102     memset(instack,0,sizeof(instack));103 }104 105 int main()106 {107     while(~scanf("%d%d",&n,&m))108     {109         init();110         for(int i=1;i<=n;i++)111             scanf("%d",val+i),val[i]=max(0,val[i]);112         for(int u,v;m--;)113             scanf("%d%d",&u,&v),ins(u+1,v+1,hed);114         for(int i=1;i<=n;i++) if(!dfn[i]) DFS(i);115         Get_map();116         for(int i=1;i<=sumcol;i++)117             if(!rd[i]) ans=max(ans,SPFA(i));118         printf("%d\n",ans);119     }120     return 0;121 }