侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【SPFA算法】最优贸易

GabrielxD
2023-03-06 / 0 评论 / 0 点赞 / 117 阅读 / 2,053 字
温馨提示:
本文最后更新于 2023-03-06,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

341. 最优贸易 - AcWing题库


CC 国有 nn 个大城市和 mm 条道路,每条道路连接这 nn 个城市中的某两个城市。

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

mm 条道路中有一部分为单向通行的道路,一部分为双向通行的道路,双向通行的道路在统计条数时也计为 11 条。

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

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

商人阿龙来到 CC 国旅游。

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

CCnn 个城市的标号从 1n1 \sim n ,阿龙决定从 11 号城市出发,并最终在 nn 号城市结束自己的旅行。

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

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

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

现在给出 nn 个城市的水晶球价格, mm 条道路的信息(每条道路所连接的两个城市的编号以及该条道路的通行情况)。

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

注意:本题数据有加强。

输入格式

第一行包含 22 个正整数 nnmm ,中间用一个空格隔开,分别表示城市的数目和道路的数目。

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

接下来 mm 行,每行有 33 个正整数, xyzx,y,z ,每两个整数之间用一个空格隔开。

如果 z=1z=1 ,表示这条道路是城市 xx 到城市 yy 之间的单向道路;如果 z=2z=2 ,表示这条道路为城市 xx 和城市 yy 之间的双向道路。

输出格式

一个整数,表示答案。

数据范围

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

输入样例:

5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2

输出样例:

5

解题

方法一:SPFA算法

思路

简化题目:求从 11 走到 nn 的所有路线中先买后卖能得到的最大收益。

1n1 \to n 的所有路线表示为一个集合,把集合划分为:

S={S11n}{S12n}{S1kn}{S1nn}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}}\}

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

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

  • 先求出 1k1\to{k} 中的最小权值点用于买入( dmin[k]=min{dmin[S1],dmin[S2],,dmin[St],w[k]}dmin[k] = \min\{dmin[S_1], dmin[S_2], \dots, dmin[S_t], w[k]\} );
  • 再求出 knk\to{n} 中的最大权值点用于卖出( dmax[k]=max{dmin[S1],dmin[S2],,dmin[St],w[k]}dmax[k] = \max\{dmin[S_1], dmin[S_2], \dots, dmin[S_t], w[k]\} );
  • 作差后得到的就是最大收益( earnMax[k]=max{dmin[k],dmax[k]}earnMax[k] = \max\{dmin[k], dmax[k]\} )。

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

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

SPFA 求解时,求 dmindmin 使用正向边,求 dmaxdmax 需要用反向边。

参考: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);
    }
}
0

评论区