题目链接：https://www.lanqiao.cn/problems/506/learning/

一道dfs+贪心算法的题

这道题有一点题目上没说，就是一个作物一定只有一种方案可以杂交出来

明白这里点，我们就可以去从后往前倒着推导

要注意到 获取 a和获取b可以同时进行

贪心公式   fc = max(a,b) +  max(fa获取a的时常,fb获取b的时常) 

#include<bits/stdc++.h>
using namespace std;
const int N = 2010;
typedef pair<int, int> PII;
int w[N], f[N];
bool have[N];

vector<PII> fa[N];

int dfs(int t)
{
    for(int i = 0; i < fa[t].size(); i++)
    {
        int a = fa[t][i].first, b = fa[t][i].second;
        if(!have[a]) dfs(a);
        if(!have[b]) dfs(b);
        if(have[a] && have[b]) 
        {
            have[t] = true;
            f[t] = min(f[t], max(w[a], w[b]) + max(f[a], f[b]));//贪心本质 
            //种子c =  max a b + max 获取a的时常和获取b的时常 
            //需要明白获取a  和 获取 b  也是可以同时进行的 
        }
    }
    return f[t];
}
int main()
{
    int n, m, k, t;
    cin >> n >> m >> k >> t;
    memset(f, 0x3f3f, sizeof f);
    for(int i = 1; i <= n; i++) cin >> w[i];//输入种子成熟的时间 
    for(int i = 1; i <= m; i++)//输入已经拥有了哪些种子 
    {
        int temp;
        cin >> temp;
        have[temp] = true;
        f[temp] = 0;
    }
    for(int i = 1; i <= k; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        fa[c].push_back({a, b}); //这里是用数组下标代表c   然后  纳入两个a b杂交参数 
    }
    cout << dfs(t);
    return 0;
}