【DFS】作物杂交【蓝桥杯】

题目

作物杂交是作物栽培中重要的一步。已知有 $N$ 种作物 (编号 $1$ 至 $N$ )，第 $i$ 种作物从播种到成熟的时间为 $T_i$ 。作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。如作物 A 种植时间为 5 天，作物 B 种植时间为 7 天，则 AB 杂交花费的时间为 7 天。作物杂交会产生固定的作物，新产生的作物仍然属于 $N$ 种作物中的一种。

初始时，拥有其中 $M$ 种作物的种子 (数量无限，可以支持多次杂交)。同时可以进行多个杂交过程。求问对于给定的目标种子，最少需要多少天能够得到。

如存在 4 种作物 ABCD，各自的成熟时间为 5 天、7 天、3 天、8 天。初始拥有 AB 两种作物的种子，目标种子为 D，已知杂交情况为 A × B → C，A × C → D。则最短的杂交过程为：

第 1 天到第 7 天 (作物 B 的时间)，A × B → C。

第 8 天到第 12 天 (作物 A 的时间)，A × C → D。

花费 12 天得到作物 D 的种子。

输入描述

输入的第 1 行包含 4 个整数 $N, M, K, T$ ， $N$ 表示作物种类总数 (编号 $1$ 至 $N$ )， $M$ 表示初始拥有的作物种子类型数量， $K$ 表示可以杂交的方案数， $T$ 表示目标种子的编号。

第 2 行包含 $N$ 个整数，其中第 $i$ 个整数表示第 $i$ 种作物的种植时间 $T_i\ (1 \leq T_i \leq 100)$ 。

第 3 行包含 $M$ 个整数，分别表示已拥有的种子类型$ K_j\ (1 \leq K_j \leq M)$ 两两不同。

第 4 至 $K$ + 3 行，每行包含 3 个整数 $A, B,C$ ，表示第 $A$ 类作物和第 $B$ 类作物杂交可以获得第 $C$ 类作物的种子。

其中， $1 \leq N \leq 2000, 2 \leq M \leq N, 1 \leq K \leq 10^5, 1 \leq T \leq N$ , 保证目标种子一定可以通过杂交得到。

输出描述

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

输入输出样例

示例

输入

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

输出

样例说明

第 1 天至第 5 天，将编号 1 与编号 2 的作物杂交，得到编号 3 的作物种子。

第 6 天至第 10 天，将编号 1 与编号 3 的作物杂交，得到编号 4 的作物种子。

第 6 天至第 9 天，将编号 2 与编号 3 的作物杂交，得到编号 5 的作物种子。

第 11 天至第 16 天，将编号 4 与编号 5 的作物杂交，得到编号 6 的作物种子。

总共花费 16 天。

运行限制

最大运行时间：2s
最大运行内存: 256M

解题

方法一：DFS 记忆化搜索

思路

注意：一种种子可能有多种杂交配方，所以记录杂交配方时值要存一个列表，而不仅仅是单独一种配方。

自上而下递归求每种需求种子的最短时间，具体来说，需要 $C$ 种子：

如果 $C$ 种子已存在，则直接返回生成 $C$ 种子所需的最短时间，以避免重复计算。
如果 $C$ 种子不存在，则查询杂交生成它的所有配方，比如有 $A + B \to C$ ，则再判断 $A、B$ 种子是否存在，如果不存在，递归地计算生成 $A、B$ 所需的时间。那么杂交生成 $C$ 在该配方下所需要的时间就是 $\min(spent[A], spent[B])$ 。
计算完所有杂交生成 $C$ 的配方的所需时间后，取其中最短的时间即可。

代码

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

public class Main {
    static int n, m, k, t;
    // pt: 种子的生长时间 spent: 生成该种子所需的最短时间(已存在的为0 没有的为0x3f3f3f3f)
    static int[] pt, spent;
    // 标记种子是否存在
    static boolean[] has;
    // 杂交生成的配方: { 结果种子C: [[材料种子A, 材料种子B, 杂交所需时间], [配方2], ...], ... }
    static Map<Integer, List<int[]>> mp = new HashMap<>();

    static int dfs(int c) {
        if (has[c]) return spent[c];
        for (int[] arr : mp.get(c)) {
            int a = arr[0], b = arr[1];
            if (!has[a]) dfs(a);
            if (!has[b]) dfs(b);
            spent[c] = Math.min(spent[c], arr[2] + Math.max(spent[a], spent[b]));
        }
        has[c] = true;
        return spent[c];
    }

    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;
        pt = new int[n + 1];
        spent = new int[n + 1];
        Arrays.fill(spent, 0x3f3f3f3f);
        has = new boolean[n + 1];
        for (int i = 1; i <= n; ++i) {
            in.nextToken();
            pt[i] = (int) in.nval;
        }
        while (m-- > 0) {
            in.nextToken();
            int x = (int) in.nval;
            has[x] = true;
            spent[x] = 0;
        }
        while (k-- > 0) {
            in.nextToken();
            int a = (int) in.nval;
            in.nextToken();
            int b = (int) in.nval;
            in.nextToken();
            int c = (int) in.nval;
            mp.putIfAbsent(c, new ArrayList<>());
            mp.get(c).add(new int[]{a, b, Math.max(pt[a], pt[b])});
        }
        System.out.println(dfs(t));
    }
}

目录CONTENT

【DFS】作物杂交【蓝桥杯】

题目

解题

方法一：DFS 记忆化搜索

思路

代码

评论区