【AcWing题解/洛谷题解/USACO题解】P1948 Telephone Lines S 通信线路
题目链接AcWinghttps://www.acwing.com/problem/content/description/342/洛谷https://www.luogu.com.cn/problem/P1948前置知识1.1.1.二分法和二分答案2.2.2.单源最短路、双端队列宽度优先搜索思路分析本题解的设问主要依据AcWing的翻译所作.第一部分从设问开始——二分法的框架设问中强调需要支付的费用是最昂贵的那一条同时又强调要使最小即求最大值的最小值所以采用二分法。二分法中我们需要得到一个满足题目要求的性质。设二分得到的中间值为xxx题目要求指定路径上不超过kkk条电缆则我们就需要判断费用大于xxx的电缆总数是否小于等于kkk。如果费用大于xxx的电缆总数超过kkk则说明我就算全部都免费升级费用大于xxx的电缆也会在该部分存在电缆不免费升级那么当前中间值xxx就不是剩下电缆中最昂贵的不符合题意。对于二分法中的左右边界虽然电缆费用的范围为111到10610^6106但是如果当前数据无解我们会二分到右边界如果有解仍然有可能会到右边界为了区分这样的情况我们把二分的左右边界设为000和106110^611061。若x≤kx≤kx≤k则满足性质将midmidmid继续往前半部分推移否则不满足性质往后半部分推移。第二部分性质的判定——最短路的结合如何判定其是否满足性质呢我们可以设费用大于xxx的电缆权值为1设费用小于等于xxx的电缆权值为0再做最短路算法这样就可以算出最少需要有多少电缆费用大于xxx了。如果到达点NNN时的距离dis[N]dis[N]dis[N]小于等于kkk则说明电缆数不超过kkk条。对于边权值只有000和111的最短路我们可以使用双端队列BFS。AC代码细节上的注意点已经写入注释。#includeiostream#includecstdio#includecstring#includedequeusingnamespacestd;//注意点1边要开两倍空间因为是双向边constintN1100,M2e410,INF0x3f3f3f3f;intn,m,k;inte[M],ne[M],h[N],w[M],idx;intst[N],dis[N];dequeintq;voidadd(inta,intb,intc){w[idx]c;e[idx]b;ne[idx]h[a];h[a]idx;return;}boolcheck(intx){//注意点2st数组一定要记得初始化memset(st,0,sizeofst);memset(dis,INF,sizeofdis);dis[1]0;q.push_back(1);while(!q.empty()){intnowq.front();q.pop_front();if(st[now])continue;st[now]true;for(intih[now];i!-1;ine[i]){intje[i],vw[i]x;if(dis[j]dis[now]v){dis[j]dis[now]v;if(!v)q.push_front(j);elseq.push_back(j);}}}returndis[n]k;}intmain(){//注意点3头数组也一定要初始化memset(h,-1,sizeofh);scanf(%d%d%d,n,m,k);for(inti1;im;i){inta,b,c;scanf(%d%d%d,a,b,c);add(a,b,c);add(b,a,c);}intl0,r1e61;while(lr){intmidlr1;if(check(mid))rmid;elselmid1;}if(r1e61)printf(-1);elseprintf(%d,r);return0;}

相关新闻

AM1705工业嵌入式开发实战:ARM9核心、PRU实时单元与硬件设计详解

AM1705工业嵌入式开发实战:ARM9核心、PRU实时单元与硬件设计详解

1. 项目概述:为什么选择AM1705这颗“老将”?在嵌入式开发领域,尤其是工业控制和自动化场景,选型往往是一场在性能、成本、稳定性和长期供货之间的艰难平衡。十年前,当TI推出基于ARM926EJ-S内核的AM1705时,它…

2026/11/17 0:27:58 阅读更多 →
C++学习打卡day1

C++学习打卡day1

memset头文件&#xff1a;#include <string.h>函数原型&#xff1a;void *memset(void *ptr,int value,size_t_Size)作用&#xff1a;1.逐字节赋值-->memset&#xff08;传入内存起始地址&#xff0c;赋值为什么&#xff0c;要赋值几位&#xff09;。2.可以用于--数组…

2026/11/17 6:53:37 阅读更多 →
【数字孪生工业应用实战】第4篇:实时数据采集与多源异构数据集成:构筑数字孪生的“神经系统” —— 从协议适配到数据湖的万字实战全解

【数字孪生工业应用实战】第4篇:实时数据采集与多源异构数据集成:构筑数字孪生的“神经系统” —— 从协议适配到数据湖的万字实战全解

【数字孪生工业应用实战】第4篇:实时数据采集与多源异构数据集成:构筑数字孪生的“神经系统” —— 从协议适配到数据湖的万字实战全解 摘要 在数字孪生系统建设中,数据采集与多源异构集成是决定项目成败的第一道关卡。工业现场充斥着Modbus、OPC UA、MQTT等多种协议,数据…

2026/11/5 11:27:23 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年&#xff0c;我大部分时间都在跟浏览器标签页打交道&#xff0c;直到第一次把桌面应用跑起来&#xff0c;才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词&#xff0c;最开始是在某段时间频繁出现在同事的讨论里&#xff0c;一个用HTML…

2026/11/19 21:38:27 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介&#xff1a;亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档&#xff0c;主要面向智能锁安装人员、终端用户及售后维护者&#xff0c;帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件&#xff0c;大小4.37MB&#xff0c;内容结构清晰&#xff…

2026/11/19 21:38:49 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统&#xff0c;整车要求空载跑到8m/s&#xff0c;电机转速已经拉到额定点&#xff0c;驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令&#xff0c;转速纹丝不动&#xff0c;三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/19 21:39:09 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年&#xff0c;用它写过嵌入式驱动、做过游戏服务端&#xff0c;也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词&#xff0c;我其实挺感慨的——这门语言的难点从来不是语法多&#xff0c;而是知识点之间的耦合太深…

2026/11/19 21:36:50 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介&#xff1a;亚太天能T109滑盖智能锁产品说明书以PDF格式发布&#xff0c;适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开&#xff0c;先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能&#xff0c;再给出完整安装步骤&…

2026/11/19 21:37:45 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历&#xff1a;翻开源码注释、论文摘要或者一份专业报告&#xff0c;每个字都认识&#xff0c;连在一起却像天书。想找人聊聊&#xff0c;身边要么没人懂&#xff0c;要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型&#xff0c;几秒钟之后&a…

2026/11/19 21:36:20 阅读更多 →

日新闻

周新闻

月新闻