一、题目
1、原题链接
3305. 作物杂交
2、题目描述
作物杂交是作物栽培中重要的一步。
已知有 N 种作物 (编号 1 至 N),第 i 种作物从播种到成熟的时间为 Ti。
作物之间两两可以进行杂交,杂交时间取两种中时间较长的一方。
如作物 A 种植时间为 5 天,作物 B 种植时间为 7 天,则 AB 杂交花费的时间为 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 的种子。
输入格式
输入的第 1 行包含 4 个整数 N,M,K,T,N 表示作物种类总数 (编号 1 至 N),M 表示初始拥有的作物种子类型数量,K
表示可以杂交的方案数,T 表示目标种子的编号。第 2 行包含 N 个整数,其中第 i 个整数表示第 i 种作物的种植时间 Ti。
第 3 行包含 M 个整数,分别表示已拥有的种子类型 Kj,Kj 两两不同。
第 4 至 K+3 行,每行包含 3 个整数 A,B,C,表示第 A 类作物和第 B 类作物杂交可以获得第 C 类作物的种子。
输出格式
输出一个整数,表示得到目标种子的最短杂交时间。
样例解释
1≤N≤2000,2≤M≤N,1≤K≤105,1≤T≤N,1≤Ti≤100,1≤Kj≤M,
保证目标种子一定可以通过杂交得到。
不保证作物 A 和 B 杂交只能生成作物 C(也就是说,A×B→C 和 A×B→D 可能同时在输入中出现)
不保证作物 C 只能由作物 A 和 B 杂交生成(也就是说,A×B→D 和 A×C→D 可能同时在输入中出现)。
不保证同一杂交公式不在输入中重复出现。输入样例:
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
样例解释
第 1 天至第 5 天,将编号 1 与编号 2 的作物杂交,得到编号 3 的作物种子。
第 6 天至第 10 天,将编号 1 与编号 3 的作物杂交,得到编号 4 的作物种子。
第 6 天至第 9 天,将编号 2 与编号 3 的作物杂交,得到编号 5 的作物种子。
第 11 天至第 16 天,将编号 4 与编号 5 的作物杂交,得到编号 6 的作物种子。
总共花费 16 天。
二、解题报告
1、思路分析
思路来源:y总讲解视频
y总yyds
动态规划解法(spfa思想求解)
(1)dist数组含义:dist[i][j]
表示在杂交次数小于等于i
的方法中,生成j
所需花费的最小时间。
(2)按最后一次的杂交方式进行划分,最多可以分为k
种。
(3)转移方程:当最后一次杂交(假设为A
、B
杂交)确定后,要使总时间最小,则使将A
、B
都生成所花费的时间最小即可。即 dist[i][j]=max(dist[i-1][A],dist[i-1][B])+max(T[A],T[B])
(T[i]
代表生成i
需要花费的时间)。
(4)利用spfa进行优化:只有一个点被更新过才需要利用它来更新其他点,并且dist[][]
的第一维可以被优化。
(5)利用上述思路进行模拟即可,输出dist[t]
即为答案。文章来源:https://www.toymoban.com/news/detail-411980.html
2、时间复杂度
时间复杂度为O(n*k)文章来源地址https://www.toymoban.com/news/detail-411980.html
3、代码详解
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N=2010,M=200010; //N代表点数(作物数),M代表边数,每种作物最多可能有k种杂交方式,所以M开成N*k数量级
int h[N],e[M],ne[M],w[N],target[M],idx; //类似邻接表存储所有的杂交方式,w[]存储生成每种作物需要花费的时间,target[i]存储利用i杂交可以生成的目标种子,w[i]存储生成i需要的时间
int n,m,k,t;
int dist[N];
bool st[N];
queue<int> q;
//类似邻接表加边
void add(int a,int b,int c){
e[idx]=b;
target[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
//spfa思路来填充dist数组
void spfa(){
while(!q.empty()){
int A=q.front();
q.pop();
st[A]=false;
for(int i=h[A];i!=-1;i=ne[i]){
int B=e[i],T=target[i];
if(dist[T]>max(dist[A],dist[B])+max(w[A],w[B])){
dist[T]=max(dist[A],dist[B])+max(w[A],w[B]);
if(!st[T]){
st[T]=true;
q.push(T);
}
}
}
}
}
int main(){
cin>>n>>m>>k>>t;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++){
cin>>w[i];
}
memset(dist,0x3f,sizeof dist);
while(m--){
int x;
cin>>x;
dist[x]=0; //初始作物已有,不需要生成,所以生成时间为0
st[x]=true;
q.push(x);
}
while(k--){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c); //因为填充dist[a]和dist[b]时都需要知道利用它的杂交方式,所以得是无向边,便于访问
add(b,a,c);
}
spfa();
cout<<dist[t];
return 0;
}
三、知识风暴
Spfa算法
- spfa算法为队列优化的Bellman-Ford算法。
- 基本思想:在Bellman-Ford算法基础上,不是每次都进行松弛操作(如果存在边
(a,b,c)
,即a
到b
的边且边权为c
,而且dist[a]>dist[b]+c
(dist[i]
存储1
号点到i
号点的最短路径的长度)即可进行松弛),而是如果一个点被更新过,将它加入队列中,然后利用它来松弛其他点,然后将该点弹出,再将更新过的点加入队列中,循环往复,直到队列为空,算法结束。
到了这里,关于【蓝桥杯集训·每日一题】AcWing 3305. 作物杂交的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!