企业官网建设流程全解析

个人建网站运营.,北京杰诚 做网站,邯郸网站优化建设,上市公司网站建设题目描述又到了一年一度的明明生日了#xff0c;明明想要买 B 样东西#xff0c;巧的是#xff0c;这 B 样东西价格都是 A 元。但是#xff0c;商店老板说最近有促销活动#xff0c;也就是#xff1a;如果你买了第 I 样东西#xff0c;再买第 J 样#xff0c;那么就可以…题目描述又到了一年一度的明明生日了明明想要买 B 样东西巧的是这 B 样东西价格都是 A 元。但是商店老板说最近有促销活动也就是如果你买了第 I 样东西再买第 J 样那么就可以只花 KI,J​ 元更巧的是KI,J​ 竟然等于 KJ,I​。现在明明想知道他最少要花多少钱。输入格式第一行两个整数A,B。接下来 B 行每行 B 个数第 I 行第 J 个为 KI,J​。我们保证 KI,J​KJ,I​ 并且 KI,I​0。特别的如果 KI,J​0那么表示这两样东西之间不会导致优惠。注意 KI,J​可能大于A。输出格式一个整数为最小要花的钱数。输入输出样例输入 #1复制运行1 1 0输出 #1复制运行1输入 #2复制运行3 3 0 2 4 2 0 2 4 2 0输出 #2复制运行7说明/提示样例解释 2。先买第 2 样东西花费 3 元接下来因为优惠买 1,3 样都只要 2 元共 7 元。同时满足多个“优惠”的时候聪明的明明当然不会选择用 4 元买剩下那件而选择用 2 元。数据规模对于 30% 的数据1≤B≤10。对于 100% 的数据1≤B≤500,0≤A,KI,J​≤1000。2018.7.25新添数据一组1. 题目背景与分析问题描述明明要买B样东西每样东西的基础价格是A。商店提供优惠策略如果你买了第I样东西再买第 J样花费只需要K_I,J元。题目给出了一个邻接矩阵表示这些优惠价格。特别地如果 K_I,J0 表示没有优惠除了自己对自己。即使有优惠K_I,J 也可能比原价A还要贵。求最小总花费。核心模型乍一看这似乎是一个复杂的动态规划或者贪心问题。但我们仔细分析我们要“买完所有物品”相当于遍历所有节点。我们要“花费最少”相当于边的权值和最小。物品之间的优惠关系构成了图的边。这就变成了一个经典的最小生成树问题。2. 难点与突破口这道题与普通MST有两个不同点入场券问题普通的MST假设所有点已经在图里只需连线。但这道题里你获得第一个物品或者断开优惠链条重新购买需要花费原价A。坑点优惠价K_I,J可能比原价A还贵。聪明的明明当然会选择直接花A元购买而不是用更贵的优惠。解决方案Prim 算法初始化通常我们做Prim算法时dis数组记录节点到当前生成树集合的最小距离会初始化为无穷大。但在本题中每个物品都有一个保底价格A。我们可以想象有一个“虚拟源点商店老板”他连接着所有物品边权都是A。初始化策略将dis数组全部初始化为A。这意味着对于任何物品我们最坏的情况就是花原价A买下来。更新策略在松弛操作时只有当优惠价g[u][v]小于当前记录的花费dis[v]时才更新。3. 算法选择数据规模B500。图的类型题目直接给出了邻接矩阵这是一个典型的稠密图边数E约等于N^2。在稠密图中Prim算法的时间复杂度为O(N^2)而Kruskal算法是O(E log E)。对于N500Prim运算量约为2.5*10^5非常高效。因此Prim邻接矩阵是本题的最优解。4. 完整代码//这道题就是要求买完所有商品最小花费本质上是求最小生成树 //买了第I样东西再买第J样那么就可以只花 KI,J元更巧的是K I,J竟然等于KJ,I 其实就是告诉我们边权就是kij要求买完所有物品钱数最少但 KI,J可能大于A但明明肯定不会花比a还多的钱去买的 因为给出了邻接矩阵所以我们用prim邻接矩阵去做 时间复杂度O(N^2) #include iostream using namespace std; int a,b; int g[510][510];//邻接矩阵 int dis[510];//每个物品购买所需的费用到集合的距离 long long sum;//总费用最小生成树长度 const int inf0x3f3f3f3f; int vis[510];//标记每个物品是否已经购买加入集合 void prim(){ //p作为找最小dis的标记需要初始化dis[0]为无穷大 dis[0]inf; //循环b次 每次找出没有购买且离集合最近的点花费最小的物品 for(int i1;ib;i){ int p0; for(int j1;jb;j){ //没有购买且价格最低 if(vis[j]0 dis[j]dis[p]) pj; } //无点可以加入当前生成树无物品可以购买 if(p0 || dis[p]inf) break; vis[p]1;//否则就标记该点已加入集合购买 sumdis[p];//更新总花费 //用p点去更新所有它的未加入集合的邻接点 //未购买且有优惠关系的物品的购买价格 for(int j1;jb;j){ //如果该物品没有购买且当前购买价格大于优惠后价格 //就更新价格 if(vis[j]0 dis[j]g[p][j]){ dis[j]g[p][j]; } } } } int main(){ cinab; //初始化要买的b样物品费用为a for(int i1;ib;i) dis[i]a; //邻接矩阵存图物品间连续购买所需要花的费用 for(int i1;ib;i){ for(int j1;jb;j){ cing[i][j]; //特别的如果K(I,J)0那么表示这两样东西之间不会导致优惠 //没有优惠就让连续购买的价格边权变为无穷大即可 if(g[i][j]0) g[i][j]inf; } } prim(); coutsum; return 0; }5. 代码细节为什么 dis[i] 初始化为a题目中K_I,J可能大于A。如果我们在Prim过程中只比较优惠价可能会选出一条很贵的边。将dis初始为 a相当于默认所有点都连向了一个“超级源点”权值为A。在后续的松弛操作 if(dis[j] g[p][j]) 中如果优惠价g[p][j]比a还要大条件不成立我们就保留了a这个更优解。关于0的处理题目输入中 0 表示两样东西之间没有导致优惠即不连通但在邻接矩阵中 0 通常表示距离极短。为了防止 Prim 算法误选这些“死路”我们需要在输入时特判if(g[i][j]0) g[i][j]inf;。时间复杂度Prim 算法包含两层循环外层遍历N个点内层寻找最小值和松弛操作也是N总复杂度 O(N^2)。对于N500的数据计算量在2.5*10^5左右完全满足时间限制。