# [Blue Bridge Cup 2020 provincial competition] [depth first search] crop hybridization (detailed explanation!)

catalogue

subject

Enter description

Output description

Test sample

sample input

sample output

Screenshot of submission results

Detailed analysis

## subject

Crop hybridization is an important step in crop cultivation. Known   N crops (No.)   one   to   N  )， The first   i   The time from sowing to maturity is   Ti. Two crops can be crossed, and the longer one of the two can be used. If the planting time of crop A is 5 days and the planting time of crop B is 7 days, the time of AB hybridization is 7 days. Crop hybridization will produce fixed crops, and the newly produced crops still belong to   N   One of two crops.

Initially, have one of them   M   The number of seeds of a crop is unlimited, which can support multiple hybridization. Multiple hybridization processes can be carried out at the same time. Ask how many days it takes to obtain a given target seed.

If there are four kinds of crops ABCD, their maturity time is 5 days, 7 days, 3 days and 8 days respectively. They initially have the seeds of two crops AB, the target seed is D, and the known hybridization situation is a × B → C，A × C → D. the shortest hybridization process is:

Day 1 to 7 (time of crop b), A × B → C.

Day 8 to 12 (time of crop A), A × C → D.

It takes 12 days to get the seeds of crop D.

Crop hybridization - Lanqiao cloud course (lanqiao.cn)https://www.lanqiao.cn/problems/506/learning/

## Enter description

Line 1 of the input contains 4 integers   N, M, K, TN,M,K,T，NN   Indicates the total number of crop types (No.)   eleven   to   NN)，MM   Indicates the number of crop seed types initially owned, KK   Indicates the number of hybridization schemes, TT   Represents the number of the target seed.

Line 2 contains   NN   Integer, where   ii   An integer represents the second   ii   Planting time of crops   T_i\ (1 \leq T_i \leq 100)Ti​   (1≤Ti​≤100).

Line 3 contains   MM   An integer representing the seed type already owned   K_j\ (1 \leq K_j \leq M)Kj​   (1≤Kj​≤M)，K_jKj​   Two different.

Paragraphs 4 to   KK  + 3 lines, each line contains 3 integers   A. B, CA, B, C, indicates the second   AA   Category crops and   BB   The second kind of crops can be obtained by hybridization   CC   The seeds of such crops.

Among them, 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 ensure that the target seed can be obtained by hybridization.

## Output description

Output an integer indicating the shortest hybridization time to obtain the target seed.

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

## Detailed analysis

1. [data structure]

How do we store all hybridization schemes for each crop?

I began to think of using two-dimensional array storage to define a sufficiently large array int hybrid[2005][2005] to store all hybridization schemes, such as a + B - > C, which is converted to hybrid[A][B] = C

However, using this storage scheme, I can't think of how to get the shortest hybridization time of a seed, because the target seed is the value stored in the array. What we need is to get all the hybridization schemes that can hybridize the seed through the label of the target seed!

So this kind of scheme is definitely not feasible.

I also came up with a way to store through two-dimensional vector s.

Define a two-dimensional vector < vector < parent > > hybrid (2005); store all hybridization schemes of each crop

Define a structure storage scheme

struct parent / / store hybrid scheme
{
int x;
int y;
};

Each time a hybridization scheme (parent type storage) that can hybridize x crops is input, it is stored in hybrid[x].

2. [recursive solution]

The recursive part is written in detail in the code, so I won't write it in detail. If you don't understand, please comment!

## Source code with detailed comments

#include <iostream>
#include <algorithm>
#include "string.h"
#include <vector>
using namespace std;

struct parent //Storage hybridization scheme
{
int x;
int y;
};
int n, m, k, t, tmp;
long long plant_time[2005];//Planting time of each crop
bool flag[2005];//Mark whether the crop appears
long long min_hybrid_time[2005];//The shortest time to cross out each crop
vector< vector<parent> >hybrid(2005);//Store all hybridization schemes for each crop

long long solve(int now)
{
if (flag[now])//If there is already the shortest time to cross out the crop
return min_hybrid_time[now];//Just return directly

for (int i = 0; i < hybrid[now].size(); i++)//Try all the schemes that can hybridize the current crop
{
parent tmp = hybrid[now][i];//The i-th scheme that can hybridize the current crop
//The shortest hybridization time of the current crop is the shortest time in all schemes for hybridizing the crop
//The shortest time for each scheme is the time required to grow their 'parent' crops + the shortest time required for their parent crops to cross (= the maximum of the time required for both crosses)
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)));
}
flag[now] = true;//Marker has found the shortest hybridization time
return min_hybrid_time[now];//Return minimum hybridization time
}

int main()
{
cin >> n >> m >> k >> t;
memset(min_hybrid_time, 0x3f, sizeof(min_hybrid_time));//The shortest time for hybridizing each crop is initialized to the maximum value
memset(flag, false, sizeof(flag));//Crop marker initialization
//Note that the subscript of the crop starts from 1!!!
for (int i = 1; i <= n; i++)//Enter planting time
cin >> plant_time[i];
for (int i = 0; i < m; i++)//Enter initial seed data
{
cin >> tmp;
flag[tmp] = true;//The marker already has the shortest hybridization time
min_hybrid_time[tmp] = 0;//Minimum hybridization time = 0 because hybridization is not required
}
for (int i = 0; i < k; i++)//Enter all hybridization schemes
{
parent temp;
cin >> temp.x >> temp.y >> tmp;
hybrid[tmp].push_back(temp);//Storage hybridization scheme
}
solve(t);//Recursive solution
cout << min_hybrid_time[t] << endl;//Output the shortest time to hybridize the target crop
return 0;
}

Keywords: search engine

Added by uidzer0 on Thu, 21 Oct 2021 19:52:51 +0300