AcWing 341. 最优贸易

题目传送门

一、为什么不能使用 dijkstra 求解本题

由于这题数据过大，如果用 \(dijkstra\) 算法必须要堆优化，而堆优化的前提是每个点只能进堆一次，很明显，这题并不是单纯地把权值累加，是求最大/最小值，所以一个点可能会进多次，与前提矛盾，只能使用 \(SPFA\) 。

二、DFS解法

#include 
using namespace std;
const int N = 110000;
const int INF = 0x3f3f3f3f;
vector way_min[N];
vector way_max[N]; //我这里用vector记录数组，大家可以使用邻接矩阵
int w[N];               //每个点的价值
int mins[N], maxs[N];   //一路走来，能获取到的最小买入价值与最大卖出价值

//从1号点出发，一路过来，标记每个点时可以获取到的最小价值
void dfs_min(int step, int v) {
    //这里没有if(step==n+1)之类的判断，因为图嘛，有边就派任务，没有边就不派任务了

    //走到当前步，携带的最小价值是v,问题是原来算过更小的，此分枝需要剪掉
    //这个剪枝剪的漂亮！
    if (v >= mins[step]) return; //该点已有更优解，无需再次搜索

    //携带过来的最小值，与当前点上的最小值PK,取得包括当前点上最小值在内的最小值
    v = min(v, w[step]);
    mins[step] = v; //更新最优解
    //枚举所有边，继续深搜
    for (int i = 0; i < way_min[step].size(); i++)
        dfs_min(way_min[step][i], v); //遍历相邻的点
}
//这个函数和上一个函数差不多，这里不再赘述
void dfs_max(int step, int v) {
    if (v <= maxs[step]) return;
    v = max(v, w[step]);
    maxs[step] = v;
    for (int i = 0; i < way_max[step].size(); i++)
        dfs_max(way_max[step][i], v);
}
int main() {
    //初始后结果数组
    memset(mins, 0x3f, sizeof mins);
    memset(maxs, -0x3f, sizeof maxs);

    int n, m; //城市的数目和道路的数目
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[i]; //点的价值

    //如果 z=1，表示这条道路是城市x到城市y之间的单向道路
    //如果 z=2，表示这条道路为城市x到城市y之间的双向道路
    int x, y, z;
    while (m--) {
        cin >> x >> y >> z;
        way_min[x].push_back(y); //这里表示求最小值所需的路径
        //反向建边
        /*
        这里有意思，必须反向建边，原因是求最大值那条路径，结尾必须是n!
        如果我们还是正向建边，那么dfs也可以求出最大值，但这条路径未必可以到达n!
        在反向建边的情况下，因为从n出发，必须可以到达n(废话！),也就是在求“经过
        n的所有路径中点权值最大是多少”

        然后正反所有方案根据点去枚举，找出都到达的点，并且最大值与最小值差最大的
        就OK了！
        */
        way_max[y].push_back(x); //因为最大值是从n开始(从i到n可转化为从n到i)，所以我们把所有路径倒个头
        //双向边
        if (z == 2) {
            way_min[y].push_back(x);
            way_max[x].push_back(y);
        }
    }
    dfs_min(1, w[1]); //从1开始遍历最小值
    dfs_max(n, w[n]); //从n开始遍历最大值
    //每个中间点都可能是答案,枚举每个点，计算最大值与最小值的差
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, maxs[i] - mins[i]);
    cout << ans << endl;
    return 0;
}

三、SPFA解法

#include 
using namespace std;
const int N = 100005;
const int M = 2000005;
int h1[N], h2[N], e[M], ne[M], idx;
//正反建图，传入头数组指针
void add(int *hh, int a, int b) {
    e[idx] = b, ne[idx] = hh[a], hh[a] = idx++;
}
int n, m;
//记录最短，最长距离数组
int dmin[N], dmax[N];
//每个节点的价值
int w[N];

//通过传递图的头数组指针和最短最长距离数组指针，重用spfa算法
void spfa(int *h, int *d, int type) {
    queue q;
    bool st[N];
    if (type) { //求max
        q.push(n);
        d[n] = w[n];
        st[n] = true;
    } else { //求min
        q.push(1);
        d[1] = w[1];
        st[1] = true;
    }
    while (q.size()) {
        int u = q.front();
        q.pop();
        st[u] = false;
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (type) {
                int dist = max(w[j], d[u]);
                if (d[j] < dist) {
                    d[j] = dist;
                    if (!st[j]) {
                        q.push(j);
                        st[j] = true;
                    }
                }
            } else {
                int dist = min(w[j], d[u]);
                if (d[j] > dist) {
                    d[j] = dist;
                    if (!st[j]) {
                        q.push(j);
                        st[j] = true;
                    }
                }
            }
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[i];
    memset(h1, -1, sizeof h1);
    memset(h2, -1, sizeof h2);

    int x, y, z;
    while (m--) {
        cin >> x >> y >> z;
        add(h1, x, y), add(h2, y, x);
        if (z == 2) add(h1, y, x), add(h2, x, y);
    }
    //距离初始化
    memset(dmin, 0x3f, sizeof dmin);
    memset(dmax, -0x3f, sizeof dmax);
    //从1出发跑最短路
    spfa(h1, dmin, 0);
    //从n出发跑最长路
    spfa(h2, dmax, 1);
    //两边一起来找碰撞点
    int res = 0;
    for (int i = 1; i <= n; i++) res = max(res, dmax[i] - dmin[i]);
    printf("%d\n", res);
    return 0;
}