侧边栏壁纸
博主头像
GabrielxD

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

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

目 录CONTENT

文章目录

【SPFA算法】作物杂交

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

题目

3305. 作物杂交 - AcWing题库


作物杂交是作物栽培中重要的一步。

已知有 NN 种作物 (编号 11NN ),第 ii 种作物从播种到成熟的时间为 TiT_i

作物之间两两可以进行杂交,杂交时间取两种中时间较长的一方。

如作物 AA 种植时间为 55 天,作物 BB 种植时间为 77 天,则 ABAB 杂交花费的时间为 77 天。

作物杂交会产生固定的作物,新产生的作物仍然属于 NN 种作物中的一种。

初始时,拥有其中 MM 种作物的种子 (数量无限,可以支持多次杂交)。

同时可以进行多个杂交过程。

求问对于给定的目标种子,最少需要多少天能够得到。

如存在 44 种作物 ABCDABCD ,各自的成熟时间为 55 天、 77 天、 33 天、 88 天。

初始拥有 ABAB 两种作物的种子,目标种子为 DD ,已知杂交情况为 A×BCA×CDA × B → C,A × C → D

则最短的杂交过程为:

11 天到第 77 天 (作物 BB 的时间), A×BCA × B → C

88 天到第 1212 天 (作物 AA 的时间), A×CDA × C → D

花费 1212 天得到作物 DD 的种子。

输入格式

输入的第 11 行包含 44 个整数 N,M,K,TN, M, K, TNN 表示作物种类总数 (编号 11NN ), MM 表示初始拥有的作物种子类型数量, KK 表示可以杂交的方案数, TT 表示目标种子的编号。

22 行包含 NN 个整数,其中第 ii 个整数表示第 ii 种作物的种植时间 TiT_i

33 行包含 MM 个整数,分别表示已拥有的种子类型 KjK_jKjK_j 两两不同。

44K+3K + 3 行,每行包含 33 个整数 A,B,CA, B, C ,表示第 AA 类作物和第 BB 类作物杂交可以获得第 CC 类作物的种子。

输出格式

输出一个整数,表示得到目标种子的最短杂交时间。

样例解释

1N20001 \le N \le 2000 ,
2MN2 \le M \le N ,
1K1051 \le K \le 10^5 ,
1TN1 \le T \le N ,
1Ti1001 \le T_i \le 100 ,
1KjM1 \le K_j \le M ,
保证目标种子一定可以通过杂交得到。
不保证作物 AABB 杂交只能生成作物 CC (也就是说, A×BCA × B → CA×BDA × B → D 可能同时在输入中出现)
不保证作物 CC 只能由作物 AABB 杂交生成(也就是说, A×BDA × B → DA×CDA × C → D 可能同时在输入中出现)。
不保证同一杂交公式不在输入中重复出现。

输入样例:

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

输出样例:

16

样例解释

11 天至第 55 天,将编号 11 与编号 22 的作物杂交,得到编号 33 的作物种子。

66 天至第 1010 天,将编号 11 与编号 33 的作物杂交,得到编号 44 的作物种子。

66 天至第 99 天,将编号 22 与编号 33 的作物杂交,得到编号 55 的作物种子。

1111 天至第 1616 天,将编号 44 与编号 55 的作物杂交,得到编号 66 的作物种子。

总共花费 1616 天。

解题

方法一:动态规划 SPFA算法

思路

本题是用 Bellman-Ford 的本质——动态规划来思考,而因为 SPFA 算法是 Bellman-Ford 算法的宽搜优化,所以可以用 SPFA 算法进行优化。

思维过程:

image-20230307013628868

状态转移方程:f(i,j)=min(f(i,j),max(f(i1,x),f(i1,y))+max(Tx,Ty))f(i, j) = \min(f(i, j), \max(f(i-1, x), f(i-1, y)) + \max(T_x, T_y))

按照该状态表示, f(n1,t)f(n-1, t) 就是答案(得到目标种子的最短杂交时间),因为从初始种子迭代到目标种子最多只会经过 n1n-1 条边。

时间复杂度:O(NK)O(NK) ,按照本题的数据范围是 O(2×108)O(2 \times 10^8) ,显然会超时,但是加一个小优化就可以过 :如果在某一次迭代中 没有任何作物的最小花费时间被更新 ,那就说明已经找到了最优解。

另外也可以使用 SPFA 算法进行优化,首先因为状态都是从上一层转移过来的,所以动归中第一维的 ii 可以直接被优化掉,其次观察状态转移方程发现:每次只有在 f(x)f(x) 或者 f(y)f(y) 发生变化后 f(j)f(j) 才有可能被更新,所以可以直接利用 SPFA算法进行宽搜优化。

代码

Bellman-Ford 算法 + 优化
import java.util.*;
import java.io.*;

public class Main {
    static final int INF = 0x3f3f3f3f;
    static int n, m, k, t;
    static int[] times, init;
    static int[][] edges;
    
    static int bellmanFord(int dest) {
        int[] dists = new int[n + 1];
        Arrays.fill(dists, INF);
        // 一开始就有的作物不需要花时间
        for (int u : init) dists[u] = 0;
        for (int i = 0; i < n - 1; ++i) {
            int[] prev = dists.clone(); // 备份 防止更新串联
            boolean flag = false;
            for (int[] edge : edges) {
                int u = edge[0], v = edge[1], p = edge[2];
                int cost = Math.max(prev[u], prev[v]) + Math.max(times[u], times[v]);
                // 松弛操作
                if (cost < dists[p]) {
                    dists[p] = cost;
                    flag = true;
                }
            }
            // 如果本次迭代中没有
            if (!flag) break;
        }
        return dists[dest];
    }
    
    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;
        in.nextToken();
        k = (int) in.nval;
        in.nextToken();
        t = (int) in.nval;
        times = new int[n + 1];
        init = new int[m];
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            times[i] = (int) in.nval;
        }
        while (m-- > 0) {
            in.nextToken();
            init[m] = (int) in.nval;
        }
        edges = new int[k][3];
        for (int i = 0; i < k; ++i) {
            in.nextToken();
            edges[i][0] = (int) in.nval;
            in.nextToken();
            edges[i][1] = (int) in.nval;
            in.nextToken();
            edges[i][2] = (int) in.nval;
        }
        System.out.println(bellmanFord(t));
    }
}
SPFA 算法
import java.util.*;
import java.io.*;

public class Main {
    static final int INF = 0x3f3f3f3f;
    static int n, m, k, t;
    // times: 每个点的种植时间  init: 初始已经有了的点
    static int[] times, init;
    static int[] h, another, product, ne;
    static int idx;
    
    // 本题加边加的并不是传统边的概念  而是相当于是用单链表记录a可以和b一起杂交成c
    static void add(int a, int b, int c) {
        another[idx] = b;
        product[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    
    static int spfa(int dest) {
        int[] dists = new int[n + 1]; // 最短路数组 这里表示最小花费时间
        boolean[] has = new boolean[n + 1];
        Queue<Integer> que = new LinkedList<>();
        Arrays.fill(dists, INF);
        // 把所有初始就有的作物加入到队列当中
        for (int u : init) {
            dists[u] = 0;
            que.offer(u);
            has[u] = true;
        }
        while (!que.isEmpty()) {
            int u = que.poll();
            has[u] = false;
            for (int i = h[u]; i != -1; i = ne[i]) {
                // u + v -> p
                int v = another[i], p = product[i];
                int cost = Math.max(dists[u], dists[v]) + Math.max(times[u], times[v]);
                if (cost < dists[p]) {
                    dists[p] = cost;
                    // 如果原材料有更新 产物就有机会被更新
                    if (!has[p]) {
                        que.offer(p);
                        has[p] = true;
                    }
                }
            }
        }
        return dists[dest];
    }
    
    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;
        in.nextToken();
        k = (int) in.nval;
        in.nextToken();
        t = (int) in.nval;
        times = new int[n + 1];
        init = new int[m];
        h = new int[n + 1];
        Arrays.fill(h, -1);
        another = new int[k * 2];
        product = new int[k * 2];
        ne = new int[k * 2];
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            times[i] = (int) in.nval;
        }
        while (m-- > 0) {
            in.nextToken();
            init[m] = (int) in.nval;
        }
        while (k-- > 0) {
            in.nextToken();
            int a = (int) in.nval;
            in.nextToken();
            int b = (int) in.nval;
            in.nextToken();
            int c = (int) in.nval;
            add(a, b, c); // 对于a来说它可以和b杂交出c
            add(b, a, c); // 对于b来说它也可以和a杂交出c
        }
        System.out.println(spfa(t));
    }
}
2
博主关闭了所有页面的评论