蓝桥杯2020年第十一届省赛真题-作物杂交（背诵）

解题思路:

该代码是一个关于作物杂交的问题，目标是计算得到特定作物种子的最早获得时间。

首先，通过输入读取作物种类总数n、初始拥有的作物种子类型数量m、可以杂交的方案数k和目标作物种子goal。

然后，通过循环遍历读取每个作物的生长时间t[i]。

接着，通过循环遍历读取拥有的作物种子类型z，并将have_k[z]标记为true。

再然后，通过循环遍历读取每个杂交方案的u、v和w，并将杂交方案存储到结构体father中。

然后，定义一个dfs函数，用于递归搜索获得种子x的最早获得时间。

在dfs函数中，首先判断如果种子x没有杂交方案，则返回false。

然后，通过循环遍历每个杂交方案，分别获取对应的u和v。

接着，判断如果种子u没有被获得，则尝试递归搜索获得种子u。

再然后，判断如果种子v没有被获得，则尝试递归搜索获得种子v。

接下来，判断如果种子x的limtime为0，则更新limtime为max(fa[u].limtime, fa[v].limtime) + max(t[u], t[v])。

否则，更新limtime为min(fa[x].limtime, max(fa[u].limtime, fa[v].limtime) + max(t[u], t[v]))。

最后，将种子x标记为已获得，并返回true。

最后，在主函数中调用input函数读取输入，然后调用dfs函数计算得到目标种子的最早获得时间，最后输出结果。

总结起来，该代码通过递归搜索的方式计算得到特定作物种子的最早获得时间。

注意事项:

参考代码:

#include <iostream>

using namespace std;

const int MAXN = 2000+5;

int n, m, k, goal;

int t[MAXN];

bool have_k[MAXN];      //若存在该种子则标记为ture

int zajiao[MAXN][MAXN];

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,goal，

    //N 表示作物种类总数 

    //M 表示初始拥有的作物种子类型数量，

    //K 表示可以杂交的方案数

    //goal目标

    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;        //二维矩阵u与v杂交出w

        int tep = ++fa[w].num;      //新种子w的杂交方案数量

        if (t[u] < t[v])swap(u, v);     //确保u的时间最大

        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++)        //遍历获得种子x的min

    {

        int v = fa[x].v[i];

        int u = fa[x].u[i];

        if (!have_k[u]) {       //如果没有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;

}