尧图网络 高端网站定制 · 原创设计
免费咨询热线
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/9/11 22:35:50
AI论文工具全解析:提升科研效率的关键技术

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

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

📅 2026/8/23 0:36:55
AI工具组合实践:提升工作效率的核心工具与方法论

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

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

📅 2026/8/23 0:36:55
MORE NEWS

更多资讯

📰

Label Studio 标注一致性(Agreement)计算完整指南:Consensus 与 Pairwise 方法论、指标与权重配置

Label Studio 标注一致性(Agreement)计算完整指南:Consensus 与 Pairwise 方法论、指标与权重配置 【免费下载链接】label-studio Label Studio is a multi-type data labeling and annotation tool with standardized output format 项目地…

📰

Task Master Auto-Implement:Claude Code 插件中的智能任务自动实现工作流

Task Master Auto-Implement:Claude Code 插件中的智能任务自动实现工作流 【免费下载链接】claude-task-master An AI-powered task-management system you can drop into Cursor, Lovable, Windsurf, Roo, and others. 项目地址: https://gitcode.com/GitHub_Tr…

📰

Actual 怎么套用官方自定义规则示例处理收款人与转账自动化

Actual 怎么套用官方自定义规则示例处理收款人与转账自动化 【免费下载链接】actual A local-first personal finance app 项目地址: https://gitcode.com/GitHub_Trending/ac/actual 银行导入的交易收款人名称经常每笔略有不同,Actual 会为每个新名称各建一…

📰

如何用 MSAL 在 Refine 中接入 Azure AD B2C 登录?

如何用 MSAL 在 Refine 中接入 Azure AD B2C 登录? 【免费下载链接】refine A React Framework for building internal tools, admin panels, dashboards & B2B apps with unmatched flexibility. 项目地址: https://gitcode.com/GitHub_Trending/re/refine …

📰

Beads 的 MCP Server 集成指南:在无 Shell 环境中让 Coding Agent 使用 bd 管理任务

Beads 的 MCP Server 集成指南:在无 Shell 环境中让 Coding Agent 使用 bd 管理任务 【免费下载链接】beads Beads - A memory upgrade for your coding agent 项目地址: https://gitcode.com/GitHub_Trending/beads1/beads Beads(bd)…

📰

量化交易数据源怎么选?四个常用工具一张表对比

量化交易数据源怎么选?四个常用工具一张表对比 【免费下载链接】awesome-systematic-trading A curated list of awesome libraries, packages, strategies, books, blogs, tutorials for systematic trading. 项目地址: https://gitcode.com/GitHub_Trending/aw/…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

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

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

📞 💬