作物杂交（2020蓝桥杯省赛）

题目

作物杂交是作物栽培中重要的一步。已知有 N种作物 (编号 1 至 N )，第 i 种作物从播种到成熟的时间为 Ti​。作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。如作物 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, TN,M,K,T，NN 表示作物种类总数 (编号 11 至 NN)，MM 表示初始拥有的作物种子类型数量，KK 表示可以杂交的方案数，TT 表示目标种子的编号。

第 2 行包含 NN 个整数，其中第 ii 个整数表示第 ii 种作物的种植时间 T_i\ (1 \leq T_i \leq 100)Ti​ (1≤Ti​≤100)。

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

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

其中，1≤N≤2000, 2≤M≤ N, 1≤K≤10^5, 1≤T≤N 1≤N≤2000,2≤M≤N,1≤K≤105,1≤T≤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 #include <iostream>
 2 #include <algorithm>
 3 #include "string.h"
 4 #include <vector>
 5 using namespace std;
 6  
 7 struct parent //存储杂交方案
 8 {    
 9     int x;
10     int y;
11 };
12 int n, m, k, t, tmp;
13 long long plant_time[2005];//每种作物的种植时间
14 bool flag[2005];//标记是否出现了该作物
15 long long min_hybrid_time[2005];//杂交出每种作物的最短时间
16 vector< vector<parent> >hybrid(2005);//存储每种作物的所有杂交方案
17  
18 long long solve(int now)
19 {
20     if (flag[now])//若是已有杂交出该种作物的最短时间
21         return min_hybrid_time[now];//直接返回即可
22  
23     for (int i = 0; i < hybrid[now].size(); i++)//对能够杂交出当前作物的方案都尝试一下
24     {
25         parent tmp = hybrid[now][i];//能够杂交出当前作物的第i种方案
26         //当前作物的最短杂交时间是 杂交出该作物的所有方案 中的最短时间
27         //而每种方案的最短时间是种植其‘父母’作物所需要的时间 + 其父母作物杂交所需的的最短时间（=两者杂交所需时间中的最大值)
28         min_hybrid_time[now] = min(min_hybrid_time[now], max(plant_time[tmp.x], plant_time[tmp.y]) + max(solve(tmp.x), solve(tmp.y)));
29     }
30     flag[now] = true;//标记已经找到最短杂交时间
31     return min_hybrid_time[now];//返回最短杂交时间
32 }
33  
34 int main()
35 {
36     cin >> n >> m >> k >> t;
37     memset(min_hybrid_time, 0x3f, sizeof(min_hybrid_time));//杂交出每种作物的最短时间初始化为最大值
38     memset(flag, false, sizeof(flag));//作物标记初始化
39     //注意作物的下标从1开始！！！
40     for (int i = 1; i <= n; i++)//输入种植时间
41         cin >> plant_time[i];
42     for (int i = 0; i < m; i++)//输入初始种子数据
43     {
44         cin >> tmp;
45         flag[tmp] = true;//标记已经有了最短杂交时间
46         min_hybrid_time[tmp] = 0;//最短杂交时间 = 0，因为不需要杂交
47     }
48     for (int i = 0; i < k; i++)//输入所有杂交方案
49     {
50         parent temp;
51         cin >> temp.x >> temp.y >> tmp;
52         hybrid[tmp].push_back(temp);//存储杂交方案
53     }
54     solve(t);//递归求解
55     cout << min_hybrid_time[t] << endl;//输出杂交出目标作物的最短时间
56     return 0;
57 }

本来想法是二叉树，发现不一定只有两个分叉，所以不符合（不过能写出来很好啦）

然后想还是深度优先搜索和动态规划！！！

第28行yyds！！！仔细理解