【SPFA算法】最优贸易

题目

341. 最优贸易 - AcWing题库

$C$ 国有 $n$ 个大城市和 $m$ 条道路，每条道路连接这 $n$ 个城市中的某两个城市。

任意两个城市之间最多只有一条道路直接相连。

这 $m$ 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 $1$ 条。

$C$ 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。

但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。

商人阿龙来到 $C$ 国旅游。

当他得知“同一种商品在不同城市的价格可能会不同”这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚一点旅费。

设 $C$ 国 $n$ 个城市的标号从 $1 \sim n$ ，阿龙决定从 $1$ 号城市出发，并最终在 $n$ 号城市结束自己的旅行。

在旅游的过程中，任何城市可以被重复经过多次，但不要求经过所有 $n$ 个城市。

阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品——水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。

因为阿龙主要是来 $C$ 国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。

现在给出 $n$ 个城市的水晶球价格， $m$ 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。

请你告诉阿龙，他最多能赚取多少旅费。

注意：本题数据有加强。

输入格式

第一行包含 $2$ 个正整数 $n$ 和 $m$ ，中间用一个空格隔开，分别表示城市的数目和道路的数目。

第二行 $n$ 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 $n$ 个城市的商品价格。

接下来 $m$ 行，每行有 $3$ 个正整数， $x，y，z$ ，每两个整数之间用一个空格隔开。

如果 $z=1$ ，表示这条道路是城市 $x$ 到城市 $y$ 之间的单向道路；如果 $z=2$ ，表示这条道路为城市 $x$ 和城市 $y$ 之间的双向道路。

输出格式

一个整数，表示答案。

数据范围

$1 \le n \le 100000$ ,
$1 \le m \le 500000$ ,
$1 \le 各城市水晶球价格 \le 100$

输入样例：

输出样例：

解题

方法一：SPFA算法

思路

简化题目：求从 $1$ 走到 $n$ 的所有路线中先买后卖能得到的最大收益。

把 $1 \to n$ 的所有路线表示为一个集合，把集合划分为：

S=\{S_{ 1\to{1}\to{n}}\} \cup \{S_{1\to{2}\to{n}}\} \cup \dots \cup \{S_{1\to{k}\to{n}}\} \cup \dots \cup \{S_{1\to{n}\to{n}}\}

其中， $S_{1\to{k}\to{n}}$ 表示：在 $1 \to k$ 中的某个点买入（包括 $1, k$ ），在 $k \to n$ 的某个点卖出（包括 $k, n$ ）的从 $1$ 走到 $n$ 的路线集合。
我们发现，这这样划分出的集合可能会有重复，但是绝对不会有遗漏，也就是说可以把每一种情况都枚举到，那么对每一个集合求受益最大值，再对所有集合的最大值求一次最大值就可以得到答案最大收益。

求每一类划分集合的最大值：以 $S_{1\to{k}\to{n}}$ 为例，就是求在点 $k$ 前面买入，后面卖出的最大收益。求该最大收益可以使用分段的方式来求：

先求出 $1\to{k}$ 中的最小权值点用于买入（ $dmin[k] = \min\{dmin[S_1], dmin[S_2], \dots, dmin[S_t], w[k]\}$ ）；
再求出 $k\to{n}$ 中的最大权值点用于卖出（ $dmax[k] = \max\{dmin[S_1], dmin[S_2], \dots, dmin[S_t], w[k]\}$ ）；
作差后得到的就是最大收益（ $earnMax[k] = \max\{dmin[k], dmax[k]\}$ ）。

在求 $dmin[k]$ 和 $dmax[k]$ 时，由于不是拓扑图，状态的更新可能存在环，因此不能使用动态规划，只能使用求最短路的方式。

另外，我们考虑能否使用 Dijkstra 算法，如果当前 $dmin[k]$ 最小的点是 $5$ ，那么有可能存在边 $5 \to 6, 6 \to 7, 7 \to 5$ ，假设当前 $dmin[5] = 10$ ，则有可能存在 $6$ 的价格是 $11$ ，但 $7$ 的价格是 $3$ ，那么 $dmin[5]$ 的值就应该被更新成 $3$ ，因此当前最小值也不一定是最终最小值，所以 Dijkstra 算法并不适用，我们只能采用 SPFA 算法。

SPFA 求解时，求 $dmin$ 使用正向边，求 $dmax$ 需要用反向边。

参考：AcWing 341. 最优贸易 - yxc

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int INF = 0x3f3f3f3f;
    static int n, m;
    static int[] w;
    // h[0]为求dmin时用的正向边  h[1]为求dmax时的用到反向边
    static int[][] h;
    static int[] e, ne;
    static int idx;
    static int[] dists;
    static boolean[] has;
    static Queue<Integer> que;
    
    static void add(int a, int b, int type) {
        e[idx] = b;
        ne[idx] = h[type][a];
        h[type][a] = idx++;
    }
    
    // type==0求dmin  type==1求dmax
    static int[] spfa(int src, int type) {
        Arrays.fill(dists, type == 0 ? INF : -INF);
        Arrays.fill(has, false);
        dists[src] = w[src];
        que.offer(src);
        has[src] = true;
        while (!que.isEmpty()) {
            int u = que.poll();
            has[u] = false;
            for (int i = h[type][u]; i != -1; i = ne[i]) {
                int v = e[i];
                boolean updated = false;
                if (type == 0 && Math.min(dists[u], w[v]) < dists[v]) {
                    dists[v] = Math.min(dists[u], w[v]);
                    updated = true;
                } else if (type == 1 && Math.max(dists[u], w[v]) > dists[v]) {
                    dists[v] = Math.max(dists[u], w[v]);
                    updated = true;
                }
                if (updated && !has[v]) {
                    que.offer(v);
                    has[v] = true;
                }
            }
        }
        return dists.clone();
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        in.nextToken();
        m = (int) in.nval;
        w = new int[n + 1];
        h = new int[2][n + 1];
        Arrays.fill(h[0], -1);
        Arrays.fill(h[1], -1);
        e = new int[m * 4];
        ne = new int[m * 4];
        dists = new int[n + 1];
        has = new boolean[n + 1];
        que = new LinkedList<>();
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            w[i] = (int) in.nval;
        }
        while (m-- > 0) {
            in.nextToken();
            int x = (int) in.nval;
            in.nextToken();
            int y = (int) in.nval;
            in.nextToken();
            int z = (int) in.nval;
            add(x, y, 0);
            add(y, x, 1);
            if (z== 2) {
                add(y, x, 0);
                add(x, y, 1);
            }
        }
        int[] dmin = spfa(1, 0), dmax = spfa(n, 1);
        int ans = 0;
        for (int i = 1; i <= n; ++i) ans = Math.max(ans, dmax[i] - dmin[i]);
        System.out.println(ans);
    }
}

目录CONTENT

【SPFA算法】最优贸易

题目

解题

方法一：SPFA算法

思路

代码

评论区