首页 > 其他分享 >南外集训 2023.12.25 T1

南外集训 2023.12.25 T1

时间:2023-12-25 14:46:59浏览次数:40  
标签:25 le 2023.12 边权 T1 南外 长度

给定一个图,求 \(s\) 到 \(t\) 的最短路,其中路径的长度是其长度前 \(k\) 大边的长度和。\(n, k \le 1000, m\le 2000\)。

做法

枚举被算入的最小边权 \(w\),所有小于 \(w\) 的边权都可以视为 \(0\),而我们需要确保大于等于 \(w\) 的边至少走了 \(k\) 条。如何实现这一点呢?通过记录已经走了几条边只能做到 \(nmk\)。在赛场上我想到答案关于 \(k\) 或者关于 \(w\) 有着凸性/单峰性,那么可以通过二分来实现。后来被证明似乎是错的。那么怎么做呢?实际上我们可以直接假设已经走了 \(k\) 条边,如果实际上没有走,我们也把没走的补上。具体地,给所有大于等于 \(w\) 的边权减去为 \(w\),求出最短路后加上 \(kw\)。这样,如果实际上走的少了,可以当作我们凭空走了一些长度为 \(w\) 的边;如果走多了,可以当作实际上排在 \(k\) 名以后的一些边也被算了一些代价。这样对于非最优解,我们只会算劣,而最优解一定能被在恰好枚举到正确 \(w\) 的时候构造出来。于是做完了。

标签:25,le,2023.12,边权,T1,南外,长度
From: https://www.cnblogs.com/kyeecccccc/p/17926046.html

相关文章

  • PoE交换机传输距离是多少?100米?250米?
    你们好,我的网工朋友。今天和你聊聊PoE交换机,之前有系统地给你讲解过一篇,可以先回顾一下哈:《啥样的交换机才叫高级交换机?这张图告诉你》为什么都说PoE交换机好?它最显著的特点就是:可以用一根网线同时传输数据和供电,不再需要昂贵电源和安装电源,很大程度上节省了费用和时间。这就自然会......
  • 2023-12-25 无法正常关闭你的电脑 错误代码:0xc0000001 ==》试一下用windows命令【sfc
    最近我的电脑每次早上开机的时候就开始蓝屏,哪怕我晚上把它设置为睡眠模式,第二天打开还是不断蓝屏,对,不是一次,而是起码七八次!我的解决方案就是用命令去修复了一下,其实我在写这个随笔的时候我也不知道明天是否能够正常开机。先说导致蓝屏的代码:0xc0000001这个代码不一定能正确代表......
  • 【飞凌 OK113i-C 全志T113-i开发板】视频编解码测试
     前言本文测试OK113i-S开发板-视频编解码的功能OK113i-S开发板是支持视频的编解码的,下面是官方介绍的编解码功能T113-i是一种为多媒体解码平台设计的高级应用处理器。T113-i集成了64位玄铁C906RISC-VCPU,双核Cortex-A7CPU和HiFi4DSP,提供高效的计算能力。主要特性支......
  • 【飞凌 OK113i-C 全志T113-i开发板】测试实时系统
    前言OK113i-S开发板上测试实时linux系统的效果Linux下的实时系统有三种方案:这三种方案各有优缺点1.PREEMPT-RT:PREEMPT-RT是一个基于Linux内核的实时补丁,也被称为Real-Time(RT)补丁。它通过增加内核的可抢占性,使得Linux内核能够实现实时性能。PREEMPT-RT补丁提供了可配置的实时选项,可......
  • 牛客周赛:25
    模板A、小红购物跳转原题点击此:[A题地址](A-小红购物_牛客周赛Round25(nowcoder.com))1、题目大意  小红购买了n件物品,但是对其中部分商品不满意要退货,但是退货要收取手续费,手续为为\(max(5,\lfloor{该商品价格/100}\rfloor)\),问你小红最终需要支出多少钱。2、题目......
  • 2023-2024-1 20231425《计算机基础与程序设计》第十三周学习总结
    2023-2024-120231425《计算机基础与程序设计》第十三周学习总结2023-2024-120231425《计算机基础与程序设计》第十三周学习总结作业信息这个作业属于哪个课程2023-2024-1《计算机基础与程序设计》这个作业要求在哪里2023-2024-1计算机基础与程序设计第十周......
  • 2023-2024-1 20231325 《计算机基础与程序设计》第13周学习总结
    ###目录*作业信息*教材学习内容总结1.《c语言程序设计》第12章*基于AI的学习*上周错题*学习进度条作业信息这个作业属于哪个课程2023-2024-1《计算机基础与程序设计》这个作业的要求在哪里1.学习《C语言程序设计》第12章并完成云班课测试。作业正文......
  • 融云数智办公获 IT168「2023 年度信创卓越贡献奖」
    近期,业界知名IT垂直门户媒体 IT168 正式揭晓其年度大型评选“2023年技术卓越奖”结果,融云榜上有名。关注【融云RongCloud】,了解协同办公平台更多干货。融云数智办公作为信创领域明星产品荣获“2023年度信创卓越贡献奖”。复杂多变的世界经济环境下,技术创新依然是主旋律。人......
  • ABC251G
    提供一个本质相同,但是不需要会向量也能做,而且很好想的方法。首先发现凸包点少,也就意味着边少,考虑从边的方向寻找突破口。考虑一个凸包的本质:若干个直线划分出若干个半平面,它们的交即为这个凸包。如果一个点对于每一条直线,都在于凸包的同侧,那么这个点就在这个凸包内。这样直接暴......
  • day25 面向对象高阶
    复习@classmethod方法类内部使用@classmethod修饰器的方法就是绑定到类的方法→类方法类方法可以直接通过类调用而无需实例化def__init__(self):类的构造函数创建一个实例(对象)时自动调用在py中self和cls只是约定俗成的命名,没有特殊的含义self通常作为对象方......