蓝桥杯|历届真题:作物杂交

1.题目

【问题描述】
作物杂交是作物栽培中重要的一步。已知有$N$种作物（编号$1$至$N$），第$i$种作物从播种到成熟的时间为$T_i$。作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。如作物$A$种植时间为5天，作物$B$种植时间为7天，则$AB$杂交花费的时间为7天。作物杂交会产生固定的作物，新产生的作物仍然属于N种作物中的一种。
初始时，拥有其中$M$种作物的种子（数量无限，可以支持多次杂交）。同时可以进行多个杂交过程。求问对于给定的目标种子，最少需要多少天能够得到。
如存在4种作物$ABCD$，各自的成熟时间为5天、7天、3天、8天。初始拥有AB两种作物的种子，目标种子为$D$，已知杂交情况为$A \times B→C，A \times C→D$。则最短的杂交过程为：

第1天到第7天（作物B的时间），$A \times B→C$。
第8天到第12天（作物A的时间），$A \ times C→D$。
花费12天得到作物D的种子。

【输入格式】
输入的第1行包含4个整数$N，M，K，T，N$表示作物种类总数（编号1至$N$），$M$表示初始拥有的作物种子类型数量，$K$表示可以杂交的方案数，$T$表示目标种子的编号。
第2行包含$N$个整数，其中第i个整数表示第i种作物的种植时间T；（$1 \leq T_i \leq 100$）
第3行包含$M$个整数，分别表示已拥有的种子类型$K_j( 1 \leq K_j \leq M)$，$K_j$两两不同。
第4至$K+3$行，每行包含3个整数$A，B，C$，表示第$A$类作物和第$B$类作物杂交可以获得第$C$类作物的种子。

【输出格式】
输出一个整数，表示得到目标种子的最短杂交时间。
【样例输入】

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

【样例说明】
第1天至第5天，将编号1与编号2的作物杂交，得到编号3的作物种
第6天至第10天，将编号1与编号3的作物杂交，得到编号4的作物种
第6天至第9天，将编号2与编号3的作物杂交，得到编号5的作物种
第11天至第16天，将编号4与编号5的作物杂交，得到编号6的作物种
总共花费16天
【评测用例规模与约定】
对于所有评测用例，$1 \leq N \leq 2000,2 \leq M \leq N，1 \leq K \leq 100000,1 \leq T \leq N$，保证目标种子一定可以通过杂交得到。

2. 题解

2.1 思路分析

思路1：暴力求解
设置一个数字minGetTime用于保存每类种子的最小获取时间
循环遍历杂交方案：
    minGetTime[C] = min(minGetTime[C],maxAB获取时间+maxAB成熟数据)
    直至数组minGetTime收敛(不再有任何位置发生变化)

2.2 代码实现

import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);
    
    // 判断minGetTime数组是否收敛|是否存在某位发生修改 无则返回true
    public static boolean isNoChange(boolean[] changeFlag){
        boolean res = true;
        for (int i = 0; i < changeFlag.length; i++) {
            res = res&changeFlag[i];
        }
        return res;
    }


    public static void main(String[] args) {
        int N = scanner.nextInt(); // 作物种类数
        int M = scanner.nextInt(); // 初始时候拥有的种子数量
        int K = scanner.nextInt(); // 可以杂交的方案数量
        int T = scanner.nextInt(); // 目的种子编号

        int[] timeSpendArr = new int[N];// 作物成熟时间
        for (int i = 0; i < N; i++) {
            timeSpendArr[i] = scanner.nextInt();
        }

        int[] startSeedArr = new int[M]; //初始拥有的种子
        for (int i = 0; i < M; i++) {
            startSeedArr[i] = scanner.nextInt();
        }

        int[][] methodArr = new int[K][3]; //杂交方案数
        for (int i = 0; i < K; i++) {
            for (int j = 0; j < 3; j++) {
                methodArr[i][j] = scanner.nextInt();
            }
        }

        int[] minGetTime = new int[N];//最小获取时间

        // 初始化最小获取时间
        for (int i = 0; i < N; i++) {
            minGetTime[i] = Integer.MAX_VALUE;
        }
        for (int i = 0; i < M; i++) {
            minGetTime[startSeedArr[i]-1] = 0;
        }

        boolean[] changeFlag = new boolean[K];//用于判断本轮处理杂交方案是否导致了最小时间发生修改|判断收敛
        Arrays.fill(changeFlag,false);
        while (!isNoChange(changeFlag)){//知道未发生修改位置
            Arrays.fill(changeFlag,true);
            for (int i = 0; i < K; i++) {
                int seedA = methodArr[i][0]-1;
                int seedB = methodArr[i][1]-1;
                if(minGetTime[seedA]==Integer.MAX_VALUE||minGetTime[seedB]==Integer.MAX_VALUE)continue;
                int newSeed = methodArr[i][2]-1;//新品种
                int minGetTimeOfNewSeed = Math.min(minGetTime[newSeed],Math.max(minGetTime[seedA],minGetTime[seedB])+Math.max(timeSpendArr[seedA],timeSpendArr[seedB]));
                if(minGetTimeOfNewSeed!=minGetTime[newSeed]){
                    changeFlag[i] = false;
                    minGetTime[newSeed] = minGetTimeOfNewSeed;
                }
            }
        }

        System.out.println(minGetTime[T-1]);
    }
}

2.3 提交结果

参考资料

1. http://lx.lanqiao.cn/problem.page?gpid=T2859