企业官网建设流程全解析

网站怎么放到服务器上,wordpress打造官网,做电商网站价钱,吉林高端网站建设信奥赛C提高组csp-s之倍增算法思想及应用案例#xff08;4#xff09; 题目描述 A 国有 nnn 座城市#xff0c;编号从 111 到 nnn#xff0c;城市之间有 mmm 条双向道路。每一条道路对车辆都有重量限制#xff0c;简称限重。 现在有 qqq 辆货车在运输货物#xff0c;司…信奥赛C提高组csp-s之倍增算法思想及应用案例4题目描述A 国有n nn座城市编号从1 11到n nn城市之间有m mm条双向道路。每一条道路对车辆都有重量限制简称限重。现在有q qq辆货车在运输货物司机们想知道每辆车在不超过车辆限重的情况下最多能运多重的货物。输入格式第一行有两个用一个空格隔开的整数n , m n,mn,m表示 A 国有n nn座城市和m mm条道路。接下来m mm行每行三个整数x , y , z x, y, zx,y,z每两个整数之间用一个空格隔开表示从x xx号城市到y yy号城市有一条限重为z zz的道路。注意x ≠ y x \neq yxy两座城市之间可能有多条道路。接下来一行有一个整数q qq表示有q qq辆货车需要运货。接下来q qq行每行两个整数x , y x,yx,y之间用一个空格隔开表示一辆货车需要从x xx城市运输货物到y yy城市保证x ≠ y x \neq yxy。输出格式共有q qq行每行一个整数表示对于每一辆货车它的最大载重是多少。如果货车不能到达目的地输出− 1 -1−1。输入输出样例 #1输入 #14 3 1 2 4 2 3 3 3 1 1 3 1 3 1 4 1 3输出 #13 -1 3说明/提示对于30 % 30\%30%的数据1 ≤ n 1000 1 \le n 10001≤n10001 ≤ m 10 , 000 1 \le m 10,0001≤m10,0001 ≤ q 1000 1\le q 10001≤q1000对于60 % 60\%60%的数据1 ≤ n 1000 1 \le n 10001≤n10001 ≤ m 5 × 10 4 1 \le m 5\times 10^41≤m5×1041 ≤ q 1000 1 \le q 10001≤q1000对于100 % 100\%100%的数据1 ≤ n 10 4 1 \le n 10^41≤n1041 ≤ m 5 × 10 4 1 \le m 5\times 10^41≤m5×104$1 \le q 3\times 10^4 $0 ≤ z ≤ 10 5 0 \le z \le 10^50≤z≤105。60分代码最大生成树 BFS查询#includebits/stdc.husingnamespacestd;constintN1e410;// 最大节点数constintM5e410;// 最大边数constintINF0x3f3f3f3f;// 无穷大值intn,m,q;// 节点数边数查询数// 边结构体structnode{intx,y,z;// 边的两个端点和权重}a[M];structnode2{intto,w;};// 比较函数按边权从大到小排序boolcmp(node a,node b){returna.zb.z;}intfa[N];// 并查集数组// 并查集查找函数intfind(intx){if(fa[x]!x)fa[x]find(fa[x]);returnfa[x];}// 并查集合并函数voidunionSet(intx,inty){introotxfind(x);introotyfind(y);if(rootxrooty)return;fa[rooty]rootx;}vectornode2g[N];// 最大生成树的邻接表// BFS查找两点间路径上的最小边权intbfs(ints,inte){// 如果起点和终点不在同一个连通分量直接返回-1if(find(s)!find(e))return-1;vectorintminw(n1,-1);// 记录到达每个节点的路径上的最小边权queueintq;minw[s]INF;// 起点到自己的最小边权设为无穷大q.push(s);while(!q.empty()){intuq.front();q.pop();if(ue)returnminw[u];// 到达终点返回结果// 遍历当前节点的所有邻居for(autox:g[u]){intvx.to;// 邻居节点intwx.w;// 边权if(minw[v]-1){// 如果邻居节点还未访问过minw[v]min(minw[u],w);// 更新到v的最小边权q.push(v);}}}return-1;}intmain(){cinnm;// 输入所有边for(inti1;im;i){cina[i].xa[i].ya[i].z;}// 按边权从大到小排序sort(a1,am1,cmp);// 初始化并查集for(inti1;in;i)fa[i]i;// 构建最大生成树for(inti1;im;i){intua[i].x;intva[i].y;intwa[i].z;if(find(u)!find(v)){// 如果两个节点不在同一个连通分量unionSet(u,v);// 合并g[u].push_back({v,w});// 在生成树中添加边g[v].push_back({u,w});}}// 处理查询cinq;while(q--){intx,y;cinxy;coutbfs(x,y)endl;// 输出两点间路径上的最小边权}return0;}60分代码功能分析算法思路最大生成树构建将边按权重从大到小排序使用Kruskal算法构建最大生成树这样保证任意两点间的路径上的最小边权是最大的查询处理对于每个查询(x, y)在最大生成树上进行BFS在BFS过程中维护从起点到当前节点的路径上的最小边权到达终点时该值即为所求关键特性正确性保证最大生成树保证了任意两点间路径的最小边权是原图中所有可能路径中最大的效率优化预处理构建生成树后每个查询可以在O(n)时间内完成连通性检查使用并查集快速判断两点是否连通时间复杂度每个查询都进行一次完整的BFS时间复杂度为O(n)查询次数q最多可达 30,000n最多可达 10,000最坏情况复杂度O(q × n) 30,000 × 10,000 3×10⁸满分代码#includebits/stdc.husingnamespacestd;constintN1e410;// 最大城市数constintM5e410;// 最大道路数constintINF0x3f3f3f3f;// 无穷大常量intn,m,q;// 存储原始道路信息structnode{intx,y,z;// x,y:城市编号, z:限重}a[M];// 存储生成树中的边structnode2{intto,w;// to:目标城市, w:边权(限重)};// 按限重从大到小排序用于构建最大生成树boolcmp(node a,node b){returna.zb.z;}// 并查集相关intfa[N];intfind(intx){if(fa[x]!x)fa[x]find(fa[x]);returnfa[x];}voidunionSet(intx,inty){introotxfind(x);introotyfind(y);if(rootxrooty)return;fa[rooty]rootx;}// LCA相关常量与数组constintLOG15;// 对数常数2^1532768 10000intd[N];// 节点深度intf[N][LOG];// f[i][j]:节点i的2^j级祖先intminw[N][LOG];// minw[i][j]:节点i到2^j级祖先路径上的最小边权vectornode2g[N];// 最大生成树的邻接表boolvis[N];// BFS访问标记// BFS预处理深度、父节点和最小边权voidbfs(intstart){queueintq;q.push(start);d[start]1;// 根节点深度为1vis[start]true;while(!q.empty()){intuq.front();q.pop();// 遍历所有邻接节点for(autox:g[u]){intvx.to;intwx.w;if(d[v])continue;// 已访问过d[v]d[u]1;// 深度1f[v][0]u;// 父节点minw[v][0]w;// 到父节点的边权vis[v]true;q.push(v);}}}// 查询从s到e路径上的最大载重(最小边权的最大值)intquery(ints,inte){// 检查是否连通if(find(s)!find(e))return-1;// 保证s的深度不小于eif(d[s]d[e])swap(s,e);intresINF;// 将s提升到与e同一深度并记录路径上的最小边权for(intiLOG-1;i0;i--){if(d[f[s][i]]d[e]){resmin(res,minw[s][i]);sf[s][i];}}// 如果此时se说明e是s的祖先if(se)returnres;// 同时提升s和e直到它们的父节点相同for(intiLOG-1;i0;i--){if(f[s][i]!f[e][i]){resmin(res,min(minw[s][i],minw[e][i]));sf[s][i];ef[e][i];}}// 最后还要比较到LCA的两条边resmin(res,min(minw[s][0],minw[e][0]));returnres;}intmain(){cinnm;// 读入所有道路for(inti1;im;i){cina[i].xa[i].ya[i].z;}// 按限重降序排序sort(a1,am1,cmp);// 初始化并查集for(inti1;in;i)fa[i]i;// 构建最大生成树for(inti1;im;i){intua[i].x;intva[i].y;intwa[i].z;if(find(u)!find(v)){unionSet(u,v);// 在生成树中添加边g[u].push_back({v,w});g[v].push_back({u,w});}}// 对每个连通分量进行BFS预处理for(inti1;in;i){if(!vis[i]){bfs(i);}}// 倍增预处理计算f和minw数组for(intk1;kLOG;k){for(inti1;in;i){f[i][k]f[f[i][k-1]][k-1];minw[i][k]min(minw[i][k-1],minw[f[i][k-1]][k-1]);}}// 处理查询cinq;while(q--){intx,y;cinxy;coutquery(x,y)endl;}return0;}满分代码功能分析算法思路问题转化将货车运输问题转化为在最大生成树上求两点间路径最小边权的问题最大生成树使用Kruskal算法构建最大生成树保证任意两点间的路径具有最大的最小边权LCA优化使用倍增法预处理树结构实现O(logN)的路径查询核心步骤预处理阶段读入数据并排序构建最大生成树BFS预处理深度和父节点倍增预处理祖先和路径最小值查询阶段检查连通性通过LCA找到路径上的最小边权时间复杂度每次查询O(logN)N最大10000查询次数q最多 30,000最坏情况复杂度O(q × logN)算法优势利用最大生成树保证最优解使用LCA倍增法实现快速查询能够处理不连通的情况更多系列知识请查看专栏《信奥赛C提高组csp-s知识详解及案例实践》https://blog.csdn.net/weixin_66461496/category_13113932.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转CSP信奥赛C一等奖通关刷题题单及题解持续更新https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转3、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html4、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}