分层图状态转移 + SPFA

其实此题可以不用强连通分量缩点，还有更优美的解法

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

分析

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

• 你可以在图上任意走动

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

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

n平方的算法不难得出：

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

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

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

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

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

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

那么 当我们进行买入操作，我们就建立一条有向边转移到一张新图上，边的大小为-v[i]，指向点i所能到达的点（在第二层图上）而这张新图就是我们的第二层图。

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

当我们进行卖出操作，我们建立一条有向边转移到第三层图上，边的大小为v[i]，指向i所能到达的点（在第三层图上）。

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

可以发现，从第一层图走到第二层图走到第三层图走到终点，这就是一个合法的选择，而且分层图把所有可能的决策都考虑到了。

最后走向终点，我们有两种合法的操作：

• 不买卖直接走向终点

直接在第一层图的n号节点建立边权为0的有向边接入一个“超级终点”

• 买卖一次后走向终点

在第三层图的n号节点建立边权为0的有向边接入“超级终点”

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

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

而我们最终的答案，就是求从第一层图的1号点，经过三层图走到“超级终点”的最长路,如图所示。

到此，这道题就解完了。参考洛谷题解：https://www.luogu.org/problemnew/solution/P1073

SPFA不仅可以用来求最短路径，也可以用来计算最长的路径
d[]数组的初始化有一些区别，求最短路径的时候，d[]初始化为+oo
求最长路径的时候，d[]初始化为-oo

#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;

const int maxn=100000+10;
const int INF = 0x3FFFFFFF;
int n,m,p[maxn];
struct Node{
    int v,w;
    Node(int v=0,int w=0):v(v),w(w){}
};

vector<Node>G[3*maxn];
int d[3*maxn],num[3*maxn];
bool in[3*maxn]; 

void add_edge(int from,int to){
    G[from].push_back(Node(to,0));
    G[from].push_back(Node(to+n,-p[from]));
    G[from+n].push_back(Node(to+n,0));
    G[from+n].push_back(Node(to+2*n,p[from]));
    G[from+2*n].push_back(Node(to+2*n,0));
}

int spfa(){
    memset(in,0,sizeof(in));
    memset(num,0,sizeof(num));
    fill(d,d+n,-INF);
    
    queue<int>que;
    que.push(0);
    in[0]=true;
    d[0]=0;
    while(!que.empty()){
        int u=que.front();
        que.pop();
        in[u]=false;
        for(int j=0;j<G[u].size();j++){
            int v=G[u][j].v;
            int w=G[u][j].w;
            if(d[v]<d[u]+w){
                d[v]=d[u]+w;
                if(in[v]==false){
                    in[v]=true;
                    que.push(v);
                }
            }
        }
    }
    return d[n-1];
}
int main(void){
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>p[i];
    for(int i=0;i<m;i++){
        int u,v,f;
        cin>>u>>v>>f;
        add_edge(u-1,v-1);
        if(f==2) add_edge(v-1,u-1);
    }
    G[n-1].push_back(Node(3*n,0));
    G[3*n-1].push_back(Node(3*n,0));
    n=3*n+1;//重新设置n的值 
    int ans=spfa();
    cout<<ans;
    return 0;
}