分层图状态转移 + SPFA

其实此题可以不用强连通分量缩点，还有更优美的解法，只需40行代码。

主要思想是类似“分层图”，或者类似“DAG”（有向无环图）的状态转移思想，特别是针对这种状态量相互影响的问题，分层图思想很实用。

分析

读完这道题，可以发现这样的事实：

• 你可以在图上任意走动

• 最终答案只与你的买入与卖出价格有关（我们就把买入卖出价值作为边权）

• 如果你买入了一个水晶球，你是没有不卖它的道理的（显然咯，买了不卖血亏...）

暴力算法不难得出：

我只关心我在哪里买了这个水晶球，在哪里把它卖出去，并且，我能否从起点走到我的买入点，从买入点走到卖出点，然后在走到 $n$

因此，先枚举两个点再bfs检查能否到达，然后更新答案。

而此题的难点在与你如何知道你是否能够到达买入，卖出，终点（即上两行 并且 后面我说的话），和你能否把所有可能的情况考虑在内。

分层图可以很好的解决这个问题。

由于可以任意走动，所以我们可以建一张图，令图上的边全都是 $0$ ，表示我的走动对我最终的结果没有影响。

考虑某个点 $i$ ，它买入或者卖出水晶球的花费是 $v_i$ 。

那么： 当我们进行买入操作，我们就建立一条有向边转移到一张新图上，边的大小为 $-v_i$ ，它从第一层的点 $i_{0}$ 指向点 $i$ 所能到达的点（在第二层图上） 指向第二层的点 $i_{1}$ 。而这张新图就是我们的第二层图。

它表示：假如我选择走了这条边，就是我在这个点买了这个水晶球，我不会反悔，并且我接下来考虑在某个点卖它。

当我们进行卖出操作，我们建立一条有向边转移到第三层图上，边的大小为 $v_i$，它从第二层的点 $i_{1}$ 指向点 $i$ 所能到达的点（在第二层图上） 指向第三层的点 $i_{2}$ 。

它表示：假如我选择走了这条边，就是我在这个点卖了这个水晶球，我不会反悔，并且我接下来考虑走向终点。

注：不能指向 $i$ 下一层到达的点，因为这样意思就变成了：我在这个点买入了水晶球，并且我一定从这个点走出去。多了一层意思就不一样了

可以发现，从第一层图走到第二层图走到第三层图走到终点，这就是一个合法的决策。

对于任何一种决策都可以抽象为我从 $1$点 走到点 $x$ 买入，然后走到点 $y$ 卖出, 然后走到点 $n$。而每一种决策都在图中对应了一条从 $1_0$ 到 $x_0$ 到 $x_1$ 到 $y_1$ 到 $y_2$ 到 $n_2$ 的路径。

所以分层图把所有合法的决策都考虑到了。而我们要求的最大收益就正好对应了图上的从 $1_0$ 到 $n_2$ 最长的路径。

注：当然也可以把边权都改成负的求个最短路(因为不存在负环也是可以的)

最后解释一下为什么我们要分层：

因为当你分了层，你就可以从还未买入这个状态，转移到已经买入准备卖出这个状态，然后在转移到从卖出点走向终点的状态。由于有向边的建立，你不能从第二/三层走回第一层图，这保证了你只做一次买卖，而不是无限做买卖，符合了题目的要求

而我们最终的答案，就是求从第一层图的 $1$ 号点，走道第三层图的 $n$ 号点的最长路,如图所示。

到此，这道题就解完了。

UPDATE 2020.10.6

其实2年前我已经退役，抱歉鸽了这么久才更新。感谢在评论中帮我指出错误，提出建议的大佬们。这次更新修改了建模，符号加入了LaTeX, 优化了代码。Hack数据已经可以通过了。如果发现了其他问题，欢迎在评论区中讨论，感谢各位的支持。

代码如下

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;

int n, m, d[maxn*3], inq[maxn*3];
vector<pair<int, int>> G[maxn*3];

#define t(x,i) (x+i*n)  // t(x,i) 表示第i层的x
// 建立x->y边的函数, 不用加 make_pair是 C++11特性
#define add(x, y) G[t(x,0)].push_back({t(y,0), 0}), G[t(x,1)].push_back({t(y,1),0}), G[t(x,2)].push_back({t(y,2),0})

void spfa(int s) {
    for(int i = 1;i <= n*3;i++) d[i] = INT_MIN; // 这里n*3别漏了, INT_MIN 是C++内置最小值常量
    d[s] = 0;
    queue<int> Q; inq[s] = true; Q.push(s);
    while(!Q.empty()) {
        int x = Q.front(); Q.pop(); inq[x] = false;
        for(auto [v, len] : G[x])  // C++17 特性, 等价于 int v = G[x][i].first, len = G[x][i].second;
            if(d[v] < d[x] + len) {
                d[v] = d[x] + len;
                if(!inq[v]) { Q.push(v); inq[v] = true; }
            }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); // 加速cin, cout
    cin >> n >> m;
    for(int i = 1, v;i <= n; ++i) {
        cin >> v;
        G[t(i,0)].push_back({t(i,1), -v});
        G[t(i,1)].push_back({t(i,2), v});
    }
    for(int i = 1,x,y,z;i <= m; ++i) {
        cin >> x >> y >> z; add(x, y);
        if(z == 2) add(y, x);
    }
    spfa(t(1,0));
    cout << d[t(n,2)] << endl;
    return 0;
}

// 分层图最长路 SPFA 算法 O(km)
#include<bits/stdc++.h>
using namespace std;

const int N=300005;
vector<pair<int,int>> e[N];
int n,m,d[N],inq[N];

void spfa(int s){
  for(int i=1;i<=n*3;i++) d[i]=-2e9; d[s]=0;
  queue<int>q;
  q.push(s),inq[s]=1;
  while(q.size()){
    int u=q.front();q.pop(),inq[u]=0;
    for(auto [v,w]:e[u]){
      if(d[v]<d[u]+w){ //最长路
        d[v]=d[u]+w;
        if(!inq[v]) q.push(v),inq[v]=1;
      }
    }
  }
}
int main(){
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  cin>>n>>m;
  for(int i=1,w;i<=n;++i){       //层间连边
    cin>>w;
    e[i].push_back({i+n,-w});    //1,2层连负权边
    e[i+n].push_back({i+2*n,w}); //2,3层连正权边
  }
  for(int i=1,x,y,z;i<=m;++i){   //层内连边
    cin>>x>>y>>z;
    e[x].push_back({y,0});
    e[x+n].push_back({y+n,0});
    e[x+2*n].push_back({y+2*n,0});
    if(z==2){
      e[y].push_back({x,0});
      e[y+n].push_back({x+n,0});
      e[y+2*n].push_back({x+2*n,0}); //均连0边权
    }
  }
  spfa(1);
  cout<<d[3*n]; //终点答案
}

建议去洛谷看题解，这个代码就是很暴力的正向反向spfa (蓝书上的方法) by: hansang

#include<bits/stdc++.h> 
using namespace std;    
const int N=1e5+10, M=5e5+10;
struct edge{int x, y, pre;} a[M], b[M]; int alen, blen, alast[N], blast[N];
void ains(int x, int y) {alen++; a[alen]=edge{x, y, alast[x]}; alast[x]=alen;}
void bins(int x, int y) {blen++; b[blen]=edge{x, y, blast[x]}; blast[x]=blen;}
int n, m, d1[N], d2[N], p[N], bv[N]; bool v[N]; deque<int> Q;
void spfa_a()
{
	memset(d1, 63, sizeof(d1)); d1[1]=p[1];
	memset(v, 0, sizeof(v)); v[1]=1;
	memset(bv, 0, sizeof(bv)); bv[1]=1;
	Q.clear(); Q.push_back(1); 
	while(!Q.empty())
	{
		int x=Q.front();
		for(int k=alast[x]; k; k=a[k].pre)
		{
			int y=a[k].y; d1[y]=min(d1[y], min(p[y], d1[x]));
			if(v[y]==0 && bv[y]<=2) v[y]=1, Q.push_back(y), bv[y]++;
		}
		Q.pop_front(); v[x]=0;
	}
}
void spfa_b()
{
	memset(d2, 0, sizeof(d2)); d2[n]=p[n];
	memset(v, 0, sizeof(v)); v[n]=1;
	memset(bv, 0, sizeof(bv)); bv[n]=1;
	Q.clear(); Q.push_back(n); 
	while(!Q.empty())
	{
		int x=Q.front();
		
		for(int k=blast[x]; k; k=b[k].pre)
		{
			int y=b[k].y; d2[y]=max(d2[y], max(p[y], d2[x]));
			if(v[y]==0 && bv[y]<=2) v[y]=1, Q.push_back(y), bv[y]++;
		}
		Q.pop_front(); v[x]=0;
	}
}
int main()
{
	alen=1; memset(alast, 0, sizeof(alast));
	blen=1; memset(blast, 0, sizeof(blast));
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++) scanf("%d", &p[i]);
	for(int i=1; i<=m; i++)
	{
		int x, y, z; scanf("%d%d%d", &x, &y, &z);
		if(z==1) ains(x, y), bins(y, x);
		else ains(x, y), ains(y, x), bins(y, x), bins(x, y);
	}
	spfa_a(); spfa_b(); int ans=0;
	for(int i=1; i<=n; i++) ans=max(ans, d2[i]-d1[i]);
	printf("%d\n", ans);
	return 0;
}