code.zip

#include<stdio.h> #include<algorithm rel='nofollow' onclick='return false;'> #define ll long long using namespace std; int n,m,ans,sum,ans2,maxx; int val[220000],rd[220000],valc[220000]; int head[220000],head2[220000],cnt=1,cntb=1; int valmax[220000]; struct note { int to; int nxt; }a[550000],b[550000]; void add(int x,int y) { a[cnt].to=y; a[cnt].nxt=head[x]; head[x]=cnt++; } void add_c(int x,int y) { b[cntb].to=y; b[cntb].nxt=head2[x]; head2[x]=cntb++; rd[y]++; } int dfn[220000],low[220000],js; int stack[330000],top,inx[220000]; int color,c[220000],ins[220000]; void tarjan(int x) { int i,j; dfn[x]=low[x]=++js; stack[++top]=x; ins[x]=1; for(i=head[x];i;i=a[i].nxt) { int to=a[i].to; if(!dfn[to]) { tarjan(to); low[x]=min(low[x],low[to]); } else if(ins[to]) { low[x]=min(low[x],dfn[to]); } } if(dfn[x]==low[x]) { color++;int y; do { y=stack[top--],ins[y]=0; c[y]=color, valc[color]+=val[y]; valmax[color]=max(valmax[color],val[y]); }while(x!=y); } } void dfs(int x) { int i,j; sum+=valc[x]; maxx=max(valmax[x],maxx); for(i=head2[x];i;i=b[i].nxt) { int to=b[i].to; dfs(to); } } int main() { int i,j,u,v; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { scanf("%d",&val[i]); } for(i=1;i<=m;i++) { scanf("%d%d",&u,&v); add(u,v); } for(i=1;i<=n;i++) { if(!dfn[i]) tarjan(i); } for(i=1;i<=n;i++) { for(j=head[i];j;j=a[j].nxt) { int to=a[j].to; if(c[to]==c[i]) continue; add_c(c[i],c[to]); } } for(i=1;i<=color;i++) { sum=0,maxx=0; if(rd[i]==0) { for(j=head2[i];j;j=b[j].nxt) { sum+=valc[i]; maxx=valmax[i]; dfs(b[j].to); if(sum>ans) { ans=sum; ans2=maxx; } sum=0,maxx=0; } } } printf("%d %d\n",ans,ans2); return 0; }