作物杂交
题目描述
作物杂交是作物栽培中重要的一步。已知有 N 种作物 (编号 1至 N )，第 i 种作物从播种到成熟的时间为 Ti 。作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。如作物 A 种植时间为 5 天，作物 B 种植时间为 7 天，则 A B 杂交花费的时间为 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 的种子。
C++
#include <iostream> using namespace std; const int MAXN = 2000+5; int n, m, k, goal; int t[MAXN]; bool have_k[MAXN]; int zajiao[MAXN][MAXN]; int limit_time; struct father { int num; int u[MAXN]; int v[MAXN]; int limtime; }fa[MAXN]; void swap(int& a, int& b) { int tep = a; a = b; b = tep; } void input() { //N,M,K,T， //N 表示作物种类总数 (编号 11 至 N)， //M 表示初始拥有的作物种子类型数量， //K 表示可以杂交的方案数，T 表示目标种子的编号。 cin >> n >> m >> k >> goal; for (int i = 1; i <= n; i++) cin >> t[i]; for (int i = 1; i <= m; i++) { int z; cin >> z; have_k[z] = true; } for (int i = 1; i <= k; i++) { int u, v, w; cin >> u >> v >> w; zajiao[u][v] = zajiao[v][u] = w; int tep = ++fa[w].num; if (t[u] < t[v])swap(u, v); fa[w].u[tep] = u; fa[w].v[tep] = v; } } bool dfs(int x) { if (fa[x].num == 0)return false; for (int i = 1; i <= fa[x].num; i++) { int v = fa[x].v[i]; int u = fa[x].u[i]; if (!have_k[u]) { if (!dfs(u))continue; } if (!have_k[v]) { if (!dfs(v))continue; } if (!fa[x].limtime) fa[x].limtime = max(fa[u].limtime, fa[v].limtime) + max(t[u], t[v]); else fa[x].limtime = min(fa[x].limtime, max(fa[u].limtime, fa[v].limtime) + max(t[u], t[v])); } have_k[x] = true; return true; } int main() { input(); dfs(goal); cout << fa[goal].limtime; return 0; }
