P1073

缩点+DAGdp，WA了8个点

#include <bits/stdc++.h>
using namespace std;
int n,m;
struct Edge
{
	int fro;
	int des;
	int next;
}edge[1000100],eg[1000100];
struct Node
{
	int st;
	int point;
	int hst;
	int dfn;
	int low;
	int ins;
	int beti;
	int maxn;
	int minn;
	int premaxn;
	int preminn;
}node[100010];
int cnt;
int dfl;
int cnl;
int tail;
int sta[100010];
inline void _Add(int x,int y)
{
	cnt++;
	edge[cnt].fro=x;
	edge[cnt].des=y;
	edge[cnt].next=node[x].st;
	node[x].st=cnt;
	return;
}
inline void Input()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&node[i].maxn);
		node[i].minn=node[i].maxn;
	}
	for(int i=1;i<=m;i++)
	{
		int u,v,z;
		scanf("%d %d %d",&u,&v,&z);
		if(z==1)
		{
			_Add(u,v);
		}
		else
		{
			_Add(v,u);
			_Add(u,v);
		}
	}
	return;
}
void dfs(int poi)
{
	dfl++;
	node[poi].dfn=dfl;
	node[poi].low=dfl;
	node[poi].ins=1;
	tail++;
	sta[tail]=poi;
	
	for(int i=node[poi].st;i!=0;i=edge[i].next)
	{
		int flag=edge[i].des;
		if(node[flag].dfn==0)
		{
			dfs(flag);
			node[poi].low=min(node[flag].low,node[poi].low); 
		}
		else
		{
			if(node[flag].ins==1)
			{
				node[poi].low=min(node[flag].low,node[poi].low);
			}
		}
	}
	if(node[poi].dfn==node[poi].low)
	{
		while(sta[tail]!=poi)
		{
			node[poi].maxn=max(node[poi].maxn,node[sta[tail]].maxn);
			node[poi].minn=min(node[poi].minn,node[sta[tail]].minn);
			node[sta[tail]].beti=poi;
			node[sta[tail]].ins=0;
			tail--;
		}
		node[sta[tail]].beti=poi;
		node[sta[tail]].ins=0;
		tail--;
	}
	return;
}
void Pre()
{
	for(int i=1;i<=cnt;i++)
	{
		int u=node[edge[i].fro].beti;
		int v=node[edge[i].des].beti;
		if(u!=v)
		{
			cnl++;
			eg[cnl].des=v;
			eg[cnl].fro=u;
			eg[cnl].next=node[u].hst;
			node[v].point++;
			node[u].hst=cnl;
		}
	}
	return;
}
int ans;
struct SB
{
	int poi;
	int minn;
};
void tuopu()
{
	queue <SB> QUE;
	SB a;
	a.minn=node[1].minn;
	a.poi=1;
	QUE.push(a);
	for(int i=1;i<=n;i++)
	{
		if(node[i].beti==i)
		{
			node[i].preminn=node[i].minn;
		}
	}
	while(!QUE.empty())
	{
		SB rnm=QUE.front();
		QUE.pop();
		for(int i=node[rnm.poi].hst;i!=0;i=eg[i].next)
		{
			int flag=eg[i].des;
			ans=max(ans,node[flag].maxn-rnm.minn);
			node[flag].preminn=min(node[flag].preminn,rnm.minn);
			node[flag].point--;
			if(node[flag].point==0)
			{
				SB fuck;
				fuck.poi=flag;
				fuck.minn=node[flag].preminn;
				QUE.push(fuck);
			}
		}
	}
	printf("%d\n",ans);
	return;
}
int main()
{
//	freopen("trade.in","r",stdin);
//	freopen("trade.out","w",stdout);
	Input();
	for(int i=1;i<=n;i++)
	{
		if(node[i].dfn==0)
		{
			dfs(i);
		}
	}
	Pre();
	
	tuopu();
	return 0;
}
/*
5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 1
3 5 1
4 5 2
*/

有点小离谱