analysis

这题太毒瘤了
留坑待补

code

#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(register int i=start;i<=end;++i)
#define anti_loop(i,start,end) for(register int i=start;i>=end;--i)
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a<b)?a:b)
#define ll long long
#define clean(arry,num) memset(arry,num,sizeof(arry))
template<typename T>void read(T &x){
	x=0;char r=getchar();T neg=1;
	while(r>'9'||r<'0'){if(r=='-')neg=-1;r=getchar();}
	while(r>='0'&&r<='9'){x=(x<<3)+(x<<1)+r-'0';r=getchar();}
	x*=neg;
}
int n,m,cnt=0,num=0,numoft=0;
const int maxn=1e5+10,maxm=1e5+10;
struct node{int e;int nxt;}edge[maxm];
int head[maxn];
int x[maxm],y[maxm];
int W[maxn],sta[maxn],top=0;
int dfn[maxn],low[maxn],belong[maxn];
int val[maxn];
inline void addl(int u,int v){
    edge[cnt].e=v;
    edge[cnt].nxt=head[u];
    head[u]=cnt++;
}
void tarjan(int u){
    dfn[u]=low[u]=++num;
    sta[++top]=u;
    for(int i=head[u];i!=-1;i=edge[i].nxt){
        int v=edge[i].e;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!belong[v])low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        belong[u]=++numoft;
        val[belong[u]]+=W[u];
        while(top>=0&&sta[top]!=u){
            belong[sta[top]]=numoft;
            //val[belong[u]]+=W[u];
            val[belong[u]]+=W[sta[top]];
            --top;
        }
        --top;
    }
}
int acc[maxn];
//inline bool cmp(int a,int b){return ((x[acc[a]]==x[acc[b]])?(y[acc[a]]<y[acc[b]]):(x[acc[a]]<x[acc[b]]));}
inline bool cmp(int a,int b){return ((x[a]==x[b])?(y[a]<y[b]):(x[a]<x[b]));}
inline void reset(){
    loop(i,1,m){
        acc[i]=i;
        x[i]=belong[x[i]];
        y[i]=belong[y[i]];
    }
    sort(acc+1,acc+1+m,cmp);
}
inline void rebuild(){
    reset();
    clean(head,-1);cnt=0;
    //loop(i,1,m){
    //    printf("_%d %d\n",x[acc[i]],y[acc[i]]);
    //}printf(">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n");
    loop(i,1,m){
        //printf("_%d %d",x[acc[i]],y[acc[i]]);
        if((x[acc[i]]!=x[acc[i-1]]||y[acc[i]]!=y[acc[i-1]])&&x[acc[i]]!=y[acc[i]]){//if((x[acc[i]]!=x[acc[i-1]]||y[acc[i]]!=y[acc[i-1]])&&belong[x[acc[i]]]!=belong[y[acc[i]]]){
            addl(x[acc[i]],y[acc[i]]);//printf("chosen\n");
        }//else printf("\n");
    }//printf(">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n");
}
int maxx=0;
int dis[maxn];
bool vis[maxn];
deque<int>q;
inline void spfa(int s){
	clean(dis,0);
	dis[s]=val[s];
	q.push_front(s);
	vis[s]=true;
	while(q.empty()==false){
        int f=q.front();q.pop_front();maxx=max(maxx,dis[f]);
        for(int i=head[f];i!=-1;i=edge[i].nxt){
            int v=edge[i].e;
            if(dis[v]<dis[f]+val[v]){
                dis[v]=dis[f]+val[v];
                vis[v]=true;//printf(">>spfa start at:%d,pos:%d,valpos:%d,from:%d,disfrom:%d,dis:%d\n",s,v,val[v],f,dis[f],dis[v]);

                if(q.empty()==false&&dis[v]>dis[q.front()])q.push_front(v);//printf("pushfront(%d)\n",v);
                else q.push_back(v);//printf("pushback(%d)\n",v);
            }
        }
	}
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("datain.txt","r",stdin);
    #endif // ONLINE_JUDGE
    clean(head,-1);clean(dfn,0),clean(low,0),clean(belong,0);clean(val,0);
    read(n),read(m);loop(i,1,n)read(W[i]);
    //loop(i,1,n)printf("%d:%d ",i,W[i]);printf("\n");
    loop(i,1,m){
        read(x[i]),read(y[i]);
        addl(x[i],y[i]);
    }
    //printf("addl\n");
    loop(i,1,n)
        if(!dfn[i])
            tarjan(i);
    //printf("belong:");loop(i,1,n)printf("%d ",belong[i]);
    //printf("\ncnt:%d\n",cnt);
    rebuild();
    //printf("numoft:%d cnt:%d\n",numoft,cnt);
    //printf("val:");loop(i,1,numoft)printf("%d ",val[i]);printf("\n");
    clean(vis,false);
    loop(i,1,numoft)
        if(!vis[i])
            //printf("spfa:%d\n",i),
				spfa(i);
    printf("%d\n",maxx);
    return 0;
}