赞
踩
试题 I: 作物杂交
时间限制: 1.0s 内存限制: 512.0MB
本题总分:25 分
【问题描述】
作物杂交是作物栽培中重要的一步。已知有 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, T,N 表示作物种类总数 (编号 1 至N),M 表示初始拥有的作物种子类型数量,K 表示可以杂交的方案数,T 表示目标种子的编号。
第 2 行包含 N 个整数,其中第 i 个整数表示第 i 种作物的种植时间Ti(1 ≤ Ti ≤ 100)。
第 3 行包含 M 个整数,分别表示已拥有的种子类型 Kj(1 ≤ Kj ≤ M),Kj两两不同。
第 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 ≤ N ≤ 2000, 2 ≤ M ≤ N, 1 ≤ K ≤ 100000, 1 ≤ T ≤ N,保证目标种子一定可以通过杂交得到。
#include <iostream> #include <vector> #include <cmath> using namespace std; const int INF = 0x3f3f3f; const int maxn = 1e5+5; struct Cross{ int a,b; }; int K[2005] = {0}; int T[2005] = {0}; int dp[2005]; vector<Cross> vec[2005]; int dfs(int _a,int _b,int _c) { if(K[_a] == 0) { for(int i = 0; i < vec[_a].size(); ++i) { dp[_a] = min(dp[_a], dfs(vec[_a][i].a, vec[_a][i].b, _a)); } } if(K[_b] == 0) { for(int i = 0; i < vec[_b].size(); ++i) { dp[_b] = min(dp[_b], dfs(vec[_b][i].a, vec[_b][i].b, _b)); } } if(K[_a] == 0 || K[_b] == 0) { return INF; } K[_c] = 1; return max(dp[_a] , dp[_b]) + max(T[_a], T[_b]); } int main() { int n,m,k,t; cin >> n >> m >> k >> t; for(int i = 0; i < 2005; ++i) { dp[i] = INF; } for(int i = 1; i <= n; ++i) { cin >> T[i]; } int j; for(int i = 1; i <= m; ++i) { cin >> j; K[j] = 1; dp[j] = 0; } int c; Cross cro; for(int i = 1; i <= k; ++i) { cin >> cro.a >> cro.b >> c; vec[c].push_back(cro); } for(int i = 0; i < vec[t].size(); ++i) { dp[t] = min(dp[t], dfs(vec[t][i].a, vec[t][i].b, t)); } cout << dp[t] << endl; return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。