#include <bits/stdc++.h>
using namespace std;
const int N = 114514;

struct Graph{
	int head[N],nxt[N*7],to[N*7];
	int cnt;
	void create_edge(int u,int v){
		cnt++;
		nxt[cnt]=head[u];
		head[u]=cnt;
		to[cnt]=v;
	}
};
struct cty{
	int mx,mn;
};
int n,m;
cty a[N];
Graph g[4];
int dfn[N];
int dfnm;
int scc[N];
bool vis[N];
map<int,int> mp;
void dfs1(int nw){
	if(vis[nw]) return ;
	vis[nw]=1;
	for(int i=g[0].head[nw];i;i=g[0].nxt[i]){
		dfs1(g[0].to[i]);
	}
	dfn[++dfnm]=nw;
	return ;
}
void dfs2(int nw,int w){
	if(vis[nw]) return ;
	vis[nw]=1;
	scc[nw]=w;
	for(int i=g[1].head[nw];i;i=g[1].nxt[i]){
		dfs2(g[1].to[i],w);
	}
}
int dfs3(int nw){
	if(vis[nw]) return -1;
	vis[nw]=1;
	for(int i=g[1].head[nw];i;i=g[1].nxt[i]){
		a[nw].mx=max(a[nw].mx,dfs3(g[1].to[i]));
	}
	return a[nw].mx;
}//max
int dfs4(int nw){
	if(vis[nw]) return 0x7f7f7f7f;
	vis[nw]=1;
	for(int i=g[1].head[nw];i;i=g[1].nxt[i]){
		a[nw].mn=min(a[nw].mn,dfs4(g[1].to[i]));
	}
	return a[nw].mn;
}//min

int main_arr(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i].mx;
		a[i].mn=a[i].mx;
		scc[i]=i;
	}
	for(int i=1;i<=m;i++){
		int wa,ac,re;
		cin>>ac>>re>>wa;
		if(wa==1){
			g[0].create_edge(ac,re);
			g[1].create_edge(re,ac);
		}else{
			g[0].create_edge(ac,re);
			g[0].create_edge(re,ac);
			g[1].create_edge(ac,re);
			g[1].create_edge(re,ac);
		}
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]) {
			dfs1(i);
		}
	}
	memset(vis,0,sizeof(vis));
	for(int i=dfnm;i>=1;i--){
		if(!vis[dfn[i]]) dfs2(dfn[i],dfn[i]);
	}
	memset(vis,0,sizeof(vis));
	for(int i=dfnm;i>=1;i--){
		if(!vis[dfn[i]]) dfs3(dfn[i]);
	}
	memset(vis,0,sizeof(vis));
	for(int i=dfnm;i>=1;i--){
		if(!vis[dfn[i]]) dfs4(dfn[i]);
	}
	for(int i=1;i<=n;i++){
		for(int j=g[0].head[i];j;j=g[0].nxt[j]){
			if(mp[scc[i]]==scc[g[0].to[j]]){
				continue;
			}else if(scc[i]==scc[g[0].to[j]]){
				continue;
			}else {
				g[2].create_edge(scc[i],scc[g[0].to[j]]);
				g[3].create_edge(scc[g[0].to[j]],scc[i]);
				mp[scc[i]]=scc[g[0].to[j]];
			}
		}
	}
	return 0;
}
int mns[N],mxe[N];
void dfs5(int nw){
	if(vis[nw]) return ;
	mns[nw]=min(mns[nw],a[nw].mn);
	vis[nw]=1;
	for(int i=g[2].head[nw];i;i=g[2].nxt[i]){
		mns[g[2].to[i]]=min(min(mns[g[2].to[i]],a[g[2].to[i]].mn),mns[nw]);
		dfs5(g[2].to[i]);
	}
}
void dfs6(int nw){
	if(vis[nw]) return ;
	mxe[nw]=max(mxe[nw],a[nw].mx);
	vis[nw]=1;
	for(int i=g[3].head[nw];i;i=g[3].nxt[i]){
		mxe[g[3].to[i]]=max(max(mxe[g[3].to[i]],a[g[3].to[i]].mx),mxe[nw]);
		//这里漏了一个dfs6(g[3].to[i]); 
	}
}
int dp(){
	for(int i=1;i<=n;i++){
		if(scc[i]==i) mxe[i]=-1;
	}
	memset(mns,0x3f,sizeof(mns));
	memset(vis,0,sizeof(vis));
	dfs5(scc[1]);
	memset(vis,0,sizeof(vis));
	dfs6(scc[n]);
	int ans=0;
	for(int i=1;i<=n;i++){
		if(scc[i]==i){
			ans=max(ans,mxe[i]-mns[i]);
		}
	}
	cout<<ans;
	return 0;
}

int main(){
	//freopen("trade.in","r",stdin);
	//freopen("trade.out","w",stdout);
	main_arr();
	dp();
	return 0;
}

如题

这么一个犯了明显错误的程序（128行）

然后： 只能说太水了