这题太毒瘤了
留坑待补
#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;}联系客服
