catalogue
Screenshot of submission results
Source code with detailed comments
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.
Title Link
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.
Test sample
sample input
6 2 4 6 5 3 4 6 4 9 1 2 1 2 3 1 3 4 2 3 5 4 5 6
sample output
16
Screenshot of submission results
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;
}