记录编号	177933	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]最优贸易	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.429 s
提交时间	2015-08-12 21:17:30	内存使用	1.93 MiB

#include <iostream>
#include <vector>
#include <fstream>
#include <queue>

using namespace std;
typedef vector<int> vi;

const int MAXN(100001), MAXM(500001);
int n, m, a[MAXN], ans = 0, f[MAXN];
ifstream fin("trade.in");
ofstream fout("trade.out");
#define cin fin
#define cout fout
void dfs(int);
inline void spfa();
bool scc[MAXN] = {false}, que[MAXN] = {false};
queue<int> q;
vi g[MAXN];

main()
{
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i){
		cin >> a[i];	//a：自己价值（计算买入时用） 
		f[i] = a[i];	//f：能到的最大价值（计算卖出时用） 
	}
	for (int i = 1; i <= m; ++i){
		int x, y;
		short z;
		cin >> x >> y >> z;
		if (z == 1)
			g[y].push_back(x);	//反向存图 
		else{
			g[x].push_back(y);
			g[y].push_back(x);
		}
	}
	fin.close();
	
	dfs(n);	//所有能到n的点都搞到scc数组中,我感觉我好机智啊！ 
	spfa();	//解释在下面的函数里 
	for (int i = 1; i <= n; ++i)
		ans = max(ans, f[i] - a[i]);
		
	cout << ans;
	fout.close();
}

void dfs(int root)
{
	if (scc[root])
		return;
	scc[root] = true;
	for (vi::iterator it = g[root].begin(); it != g[root].end(); ++it)
		dfs(*it);
}

inline void spfa(){
	for (int i = n; i > 0; --i){	//此处从终至始一个一个求f
		if(! scc[i])	//到不了终点的点滚一边去…… 
			continue;
		q.push(i);
//		que[i] = true;
		for (vi::iterator it = g[i].begin(); it != g[i].end(); ++it){
//			que[*it] = true;
			q.push(*it);
		}
		while (! q.empty()){
			int j = q.front();
			q.pop();
//			que[j] = false;
			for (vi::iterator it = g[j].begin(); it != g[j].end(); ++it){
				if (f[j] > f[*it]){	//如果j点的f值大于它前面点目前f值
					f[*it] = f[j]; 	//更新
					q.push(*it);	// 再以这个点为源点向前更新
//						que[*it] = true;
				}
			}
		} 
	}
}