尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
【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;}
RELATED

相关推荐

C++ nullptr:从类型安全到现代编程实践

C++ nullptr:从类型安全到现代编程实践

1. 项目概述:为什么我们需要nullptr在C的世界里,指针是一个绕不开的核心概念。它既是赋予程序员直接操作内存能力的“利剑”,也是无数段错误(Segmentation Fault)和内存泄漏的“万恶之源”。对于初学者而言&#xff0c…

📅 2026/11/6 15:26:34
AI论文工具全解析:提升科研效率的关键技术

AI论文工具全解析:提升科研效率的关键技术

1. 项目概述:AI论文工具为何成为学术刚需去年帮学弟改论文时,发现他还在用Word手动调整参考文献格式,这让我意识到很多研究者对AI论文工具的认知存在严重滞后。事实上,在顶级学术圈里,从文献管理到实验记录再到论文润色…

📅 2026/10/11 6:20:24
AI工具组合实践:提升工作效率的核心工具与方法论

AI工具组合实践:提升工作效率的核心工具与方法论

1. 当前AI工具生态现状观察最近两年AI领域的发展速度简直让人瞠目结舌。作为一名长期关注技术趋势的从业者,我明显感受到AI工具已经从实验室走向了日常工作和生活。现在打开任何一个应用商店或者技术论坛,都能看到数十种声称能"改变工作方式"的…

📅 2026/10/11 20:23:56
MORE NEWS

更多资讯

📰

西安电工证查询安检网官方回应:别被中介坑,这些避坑技巧必须知道

西安电工证查询安检网官方回应:别被中介坑,这些避坑技巧必须知道 你是不是也遇到过这种情况,不知道去哪里报名特种作业证,担心被中间人套路,花了不少冤枉钱,结果证还没拿到? 西安电工证查询安检网…

📰

东阳特种工考试电话保姆级教程:证书过期了不知道怎么复审延期

东阳特种工考试电话保姆级教程:证书过期了不知道怎么复审延期 证书过期了不知道怎么复审延期,是不是你最近正在经历的焦虑?别急,这篇文章就是你的 保姆级教程…

📰

诸暨考电工证哪里报名怎么报名 电工证不考没法上岗

诸暨考电工证哪里报名怎么报名 电工证不考没法上岗 工地太忙根本没时间复习考试,这几乎是所有一线电工的真实写照。你可能在钢筋水泥间穿梭了一整天,连吃饭的时间都得抓紧,哪还有精力去系统学习电工证考试内容?但现实是,…

📰

平定电工证复审要多少钱?别再被中介坑了

平定电工证复审要多少钱?别再被中介坑了 你是不是也遇到过这样的情况:手里拿着电工证,但不知道什么时候该复审、该去哪里办、要多少钱?特别是现在各种中介满天飞,一不小心就被骗钱又耽误事。今天我就用一个真实案例,带你搞清楚【平定电工证复审】到底要…

📰

温岭报考电工证多少钱?真实经历告诉你别怕学历不高也能报

温岭报考电工证多少钱?真实经历告诉你别怕学历不高也能报 你是不是也担心学历不高怕报不上名?别急,我来给你说说我的真实经历。我当年刚毕业,学历只有大专,想考电工证,也怕被拒,结果发现只要材料齐全、流程走对,其实一点都不难。…

📰

安监局电工证 成都怎么考?实操考试心里没底怕挂科?郑州报考避坑指南来了!

安监局电工证 成都怎么考?实操考试心里没底怕挂科?郑州报考避坑指南来了! 实操考试心里没底怕挂科?你是成都的电工从业者,正准备考取安监局电工证,但对考试内容、流程、材料准备都不太清楚?别急,本文就帮你把郑州报考避坑指南讲透彻,手把手带你走完…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬