网站正在升级建设中代码,中国室内设计联盟网官网,注册域名阿里云,徐州集团网站建设报价文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴Spfa算法一、题目
1、原题链接 3305. 作物杂交 2、题目描述 作物杂交是作物栽培中重要的一步。 已知有 N 种作物 (编号 1 至 N)#xff0c;第 i 种作物从播种到成熟的时间…
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴Spfa算法一、题目
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→CA×C→D。 则最短的杂交过程为 第 1 天到第 7 天 (作物 B 的时间)A×B→C。 第 8 天到第 12 天 (作物 A 的时间)A×C→D。 花费 12 天得到作物 D 的种子。 输入格式 输入的第 1 行包含 4 个整数 N,M,K,TN 表示作物种类总数 (编号 1 至 N)M 表示初始拥有的作物种子类型数量K 表示可以杂交的方案数T 表示目标种子的编号。 第 2 行包含 N 个整数其中第 i 个整数表示第 i 种作物的种植时间 Ti。 第 3 行包含 M 个整数分别表示已拥有的种子类型 KjKj 两两不同。 第 4 至 K3 行每行包含 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思想求解 1dist数组含义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]即为答案。
2、时间复杂度
时间复杂度为O(n*k)
3、代码详解
#include iostream
#include cstring
#include queue
using namespace std;
const int N2010,M200010; //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];
queueint 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 Aq.front();q.pop();st[A]false;for(int ih[A];i!-1;ine[i]){int Be[i],Ttarget[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(){cinnmkt;memset(h,-1,sizeof h);for(int i1;in;i){cinw[i];}memset(dist,0x3f,sizeof dist);while(m--){int x;cinx;dist[x]0; //初始作物已有不需要生成所以生成时间为0st[x]true;q.push(x);}while(k--){int a,b,c;cinabc;add(a,b,c); //因为填充dist[a]和dist[b]时都需要知道利用它的杂交方式所以得是无向边便于访问 add(b,a,c);}spfa();coutdist[t];return 0;
}三、知识风暴 Spfa算法 spfa算法为队列优化的Bellman-Ford算法。基本思想在Bellman-Ford算法基础上不是每次都进行松弛操作如果存在边(a,b,c)即a到b的边且边权为c而且dist[a]dist[b]cdist[i]存储1号点到i号点的最短路径的长度即可进行松弛而是如果一个点被更新过将它加入队列中然后利用它来松弛其他点然后将该点弹出再将更新过的点加入队列中循环往复直到队列为空算法结束。
