题解 | #[NOIP2009]最优贸易#

题意

在 从 1号点到 n号点 的路径中， 选择两个城市 A 和 B，必须先选 A 再选 B，问 能赚取的差价最大是多少
A：买入水晶球
B：卖出水晶球

ps：1 号点到 n 号点的路径可能不止一条 .

思路

不妨遍历 n 个点，对于每个点求出 res_i = w2[i] - w1[i]
w1[i]：买入。在从 1 到 i 的路径中，水晶球的最小价格 (若从 1 到不了 i ，则 w1[i] = 正无穷 )
w2[i]：卖出。在从 n 到 i 的路径中，水晶球的最大价格 (若从 n 到不了 i ，则 w2[i] = 0 ) // 要求我们建立反向边

因此最后的 ans = max( 0, res_1, res_2, ...... , res_n )

求 w1[ ] ：正向 spfa
求 w2[ ] ：反向 spfa ，要求我们建立反向边，比如 a ==> b 的边，我们就建立 b ==> a 的边

ps：此处不可以使用 dijkstra ，因为 dijkstra 是从起点开始依次选择距离起点最短的边，从而形成的最短路，而此题 一方面 不是让求最短路，一方面 没有边权.

综上，Code 如下.

Code

#include <bits/stdc++.h>

using namespace std;

const int N=100010,M=500010;

int a[N];
bool st1[N],st2[N];
int h1[N],e1[M],ne1[M],idx1;
int h2[N],e2[M],ne2[M],idx2;
int w1[N],w2[N];
int n,m;

void add1(int a,int b){   // 建立正向边
    e1[idx1]=b,ne1[idx1]=h1[a],h1[a]=idx1++;
}

void add2(int a,int b){  // 建立反向边
    e2[idx2]=b,ne2[idx2]=h2[a],h2[a]=idx2++;
}

void spfa1(){  // 从起点开始
    memset(w1,0x3f,sizeof w1);
    st1[1]=true;
    queue<int>q;
    q.push(1);
    w1[1]=a[1];

    while(q.size()){
        int t=q.front();
        q.pop();
        st1[t]=false;

        for(int i=h1[t];~i;i=ne1[i]){
            int j=e1[i];
            if(a[j]<w1[j]||w1[t]<w1[j]){ // 存在回路，即可能 w1[j] 比两者都小（或等于），此时不需要更新
                w1[j]=min(w1[t],a[j]);     // j 点被更新
                if(!st1[j]) st1[j]=true,q.push(j);  // 被更新的点 其 后面的点可能也需要更新 所以 j 入列
            }
        }
    }
}

void spfa2(){  //从终点开始
    st2[n]=true;
    queue<int>q;
    q.push(n);
    w2[n]=a[n];

    while(q.size()){
        int t=q.front();
        q.pop();
        st2[t]=false;
        for(int i=h2[t];~i;i=ne2[i]){
            int j=e2[i];
            if(a[j]>w2[j]||w2[t]>w2[j]){  // 原因同上
                w2[j]=max(a[j],w2[t]);  
                if(!st2[j]) st2[j]=true,q.push(j);
            }
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    memset(h1,-1,sizeof h1);
    memset(h2,-1,sizeof h2);

    while(m--){
        int x,y,z;
        cin>>x>>y>>z;
        if(z==1) add1(x,y),add2(y,x);  //同时建立反向边
        else add1(x,y),add1(y,x),add2(x,y),add2(y,x);   //同时建立反向边
    }

    spfa1();
    spfa2();

    int res=0;
    for(int i=1;i<=n;i++) res=max(res,w2[i]-w1[i]); 
    cout<<res<<endl;

    return 0;
}