洛谷 P1073 最優貿易 分層圖狀态轉移 spfa 最長路

題目連結：

https://www.luogu.org/problem/P1073

思想：

1：新的概念：分層圖

2：參考部落格：https://www.luogu.org/blog/user15019/solution-p1073，特别特别推薦，詳細了解分層圖的原理就從精讀這一個部落格開始

思路：

1：讀完這道題，可以發現這樣的事實：

      1：你可以在圖上任意走動

      2：最終答案隻與你的買入與賣出價格有關（我們就把買入賣出價值作為邊權）

      3：如果你買入了一個水晶球，你是沒有不賣它的道理的（顯然咯，買了不賣血虧...）

2：分層圖可以很好的解決這個問題：由于可以任意走動，是以我們可以建一張圖，令圖上的邊全都是0，表示我的走動對我最終的結果沒有影響，考慮某個點 i ，它買入或者賣出水晶球的花費是v[i]

3：那麼 當我們進行買入操作，我們就建立一條有向邊轉移到一張新圖上，邊的大小為-v[i]，指向點i所能到達的點（在第二層圖上）而這張新圖就是我們的第二層圖，它表示：假如我選擇走了這條邊，就是我在這個點買了這個水晶球，我不會反悔，并且我接下來考慮在某個點賣它

4：當我們進行賣出操作，我們建立一條有向邊轉移到第三層圖上，邊的大小為v[i]，指向i所能到達的點（在第三層圖上），它表示：假如我選擇走了這條邊，就是我在這個點賣了這個水晶球，我不會反悔，并且我接下來考慮走向終點

5：可以發現，從第一層圖走到第二層圖走到第三層圖走到終點，這就是一個合法的選擇，而且分層圖把所有可能的決策都考慮到了

6：最後走向終點，我們有兩種合法的操作：

     1：不買賣直接走向終點，直接在第一層圖的n号節點建立邊權為0的有向邊接入一個“超級終點”

     2：買賣一次後走向終點，在第三層圖的n号節點建立邊權為0的有向邊接入“超級終點”

7：最後解釋一下為什麼我們要分層：

      因為當你分了層，你就可以從還未買入這個狀态，轉移到已經買入準備賣出這個狀态，然後再轉移到從賣出點走向終點的狀态。由于有向邊的建立，你不能從第二或三層走回第一層圖，這保證了你隻做一次買賣，而不是無限做買賣，符合了題目的要求，而我們最終的答案，就是求從第一層圖的1号點，經過三層圖走到“超級終點”的最長路,

代碼：

1：一開始就把邊存為負權值，然後跑最短路spfa算法，取負值即為最長路

#include <bits/stdc++.h>

using namespace std;
const int maxn=1e5+1;
int n,m,a,b,c,ing[maxn*3+1],v[maxn],d[maxn*3+1];
vector<pair<int,int> >e[maxn*3+1];

inline void spfa(int s)
{
    memset(ing,0,sizeof(ing));
    memset(d,0x7f,sizeof(d));
    queue<int>q;
    q.push(s);
    d[s]=0;
    ing[s]=1;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        ing[now]=0;
        for(int i=0;i<e[now].size();i++)
        {
            int v=e[now][i].first;
            if(d[v]>d[now]+e[now][i].second)
            {
                d[v]=d[now]+e[now][i].second;
                if(ing[v])
                    continue;
                q.push(v);
                ing[v]=1;
            }
        }
    }
}

inline void addedge(int x,int y)
{
    e[x].push_back(make_pair(y,0));
    e[x+n].push_back(make_pair(y+n,0));
    e[x+2*n].push_back(make_pair(y+2*n,0));
    e[x].push_back(make_pair(y+n,v[x]));
    e[x+n].push_back(make_pair(y+2*n,-v[x]));
}

int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        addedge(a,b);
        if(c==2)addedge(b,a);
    }
    e[n].push_back(make_pair(3*n+1,0));
    e[n*3].push_back(make_pair(n*3+1,0));
    spfa(1);
    cout<<-d[3*n+1]<<endl;
    return 0;
}
           

2：求最長路的spfa算法

#include <bits/stdc++.h>

using namespace std;
const int maxn=1e5+1;
int n,m,a,b,c,ing[maxn*3+1],v[maxn],d[maxn*3+1];
vector<pair<int,int> >e[maxn*3+1];

inline void spfa(int s)
{
    memset(ing,0,sizeof(ing));
    memset(d,-0x7f,sizeof(d));
    queue<int>q;
    q.push(s);
    d[s]=0;
    ing[s]=1;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        ing[now]=0;
        for(int i=0;i<e[now].size();i++)
        {
            int v=e[now][i].first;
            if(d[v]<d[now]+e[now][i].second)
            {
                d[v]=d[now]+e[now][i].second;
                if(ing[v])
                    continue;
                q.push(v);
                ing[v]=1;
            }
        }
    }
}

inline void addedge(int x,int y)
{
    e[x].push_back(make_pair(y,0));
    e[x+n].push_back(make_pair(y+n,0));
    e[x+2*n].push_back(make_pair(y+2*n,0));
    e[x].push_back(make_pair(y+n,-v[x]));
    e[x+n].push_back(make_pair(y+2*n,v[x]));
}

int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        addedge(a,b);
        if(c==2)addedge(b,a);
    }
    e[n].push_back(make_pair(3*n+1,0));
    e[n*3].push_back(make_pair(n*3+1,0));
    spfa(1);
    cout<<d[3*n+1]<<endl;
    return 0;
}