记录编号	329961	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]最优贸易	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	0.386 s
提交时间	2016-10-25 20:26:47	内存使用	26.73 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<queue> 
#define file(x) "trade."#x
using std::min;
using std::max;
using std::swap;
const int MAXV=100010,MAXE=500010<<1;
int n,m,scnt,scid[MAXV],c[MAXV],dfn[MAXV],dfsclk,mx[MAXV],mn[MAXV],f[MAXV],f2[MAXV],ans;
std::stack<int> s;
struct NODE{int u,mn,nans;
NODE(int iu,int imn,int ia):u(iu),mn(imn),nans(ia){}
};
std::queue<NODE> q;
bool vis[MAXV];
struct G{
	struct EDGE{int u,v;}st[MAXE];
	int hed[MAXV],nxt[MAXE],sz;
	void add(int u,int v){
		st[++sz].u=u,st[sz].v=v;
		nxt[sz]=hed[u],hed[u]=sz;
	}
	void give(G& tar){
		for(int i=1;i<=sz;i++){
			int u=scid[st[i].u],v=scid[st[i].v];
			if(u==v) continue;
			swap(u,v);
			tar.add(u,v);
		}
	}
int dfs(int u){
	int lowu=dfn[u]=++dfsclk;
	s.push(u);
	for(int e=hed[u];e;e=nxt[e]) {
		int v=st[e].v;
		if(!dfn[v]) lowu=min(lowu,dfs(v));
		else if(!scid[v]) lowu=min(lowu,dfn[v]);
	}
	if(dfn[u]==lowu){
		++scnt; 
		int x;
		do{
			x=s.top();s.pop();
			mn[scnt]=min(c[x],mn[scnt]);
			mx[scnt]=max(c[x],mx[scnt]);
			scid[x]=scnt;
		}while(x!=u);
	}
	return lowu;
}
int dfs1(int u){
	if(f[u]) return f[u];
	f[u]=mn[u];
	f2[u]=mx[u]-mn[u];
	for(int e=hed[u];e;e=nxt[e]) f[u]=min(f[u],dfs1(st[e].v)),f2[u]=max(f2[u],mx[u]-f[u]);
	return f[u];
}
void solve(int u){
	int v;
	ans=max(ans,f2[u]);
	for(int e=hed[u];e;e=nxt[e]) if(!vis[v=st[e].v]){
		vis[v]=1;
		solve(v);
	}
}
}g1,g2;
int main(){
	freopen(file(in),"r",stdin);
	freopen(file(out),"w",stdout);
	memset(mn,0x3f,sizeof(mn));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&c[i]);
	for(int i=1;i<=m;i++) {
		int u,v,z;
		scanf("%d%d%d",&u,&v,&z);
		g1.add(u,v);
		if(z==2) g1.add(v,u);
	}
	for(int i=1;i<=n;i++) if(!scid[i]) g1.dfs(i);
	g1.give(g2);
	for(int i=1;i<=scnt;i++) if(!f[i]) g2.dfs1(i);
	vis[scid[n]]=1;
	g2.solve(scid[n]);
	printf("%d",ans);
}