当前位置: 首页 > news >正文

basic - graph theory

  • P2860 [USACO06JAN] Redundant Paths G
    先转化为加尽量少的边使得图为边双。 注意到边双具有传递性,则先进行缩点。(此处注意tot=1和lst^1的实现细节)
    则问题又转化为加尽可能少的边,使一个全是割点的图变成边双。
    边加在叶子上较优,在两个叶子之间加边等同于用两者之间的路径覆盖树。
    用一条边连接两个叶子,最终连上所有叶子,可以等价转化为用尽可能的链覆盖整棵树。
    经典结论:最小链数为 T 的叶子个数除以 2 上取整。 证明考虑先全部连上再对局面进行调整(典),奇数个叶子先将多出来的连到 deg≥3 的节点上。对于每条没被覆盖的边,隔开的两个连通块分别取配对的两个叶子交换覆盖(不可能只有一个叶子,因为其已经配对,肯定会穿过当前边),一定可以覆盖原有+当前边,更优。
  • P2916 [USACO08NOV] Cheering up the Cow G
    如果觉得某种方式可能不够优,记得可以重新赋边权(点权)再最优化处理。
    注意到每个点代价次数即为度数(欧拉序中一个点出现的次数也为其权值),则把点权扔到边上处理
    然后最小生成树。
  • P3623 [APIO2008] 免费道路
    首先考虑没有任何限制,求生成树,每条边都是等价的。
    如果只在鹅卵石路中选有贡献的k条边连上,可能会出现剩下边怎么连都无法连通,但实际有解的情况。因此先把非鹅卵石路都连上,把必选的鹅卵石路选出来,然后清空重新连,随便选有贡献的就好了。注意判断无解。

Shortest Path

  • CF1887B Time Travel
    别的都比较常规。跑dij的时候边权动态,显然如果要等的话等到时间最近的那个最优,对于每条边记录下属于的边集,对于每个边集记录有效时间,然后upper_bound一下即可。(返回迭代器的话end解引用是最后一个 注意特判)

Tree

  • CF1805E There Should Be a Lot of Maximums
    • 一条边分成的两个子树\(\rightarrow\)放在dfs序上拍平,一个区间,一个前缀;复制一遍,两个区间,然后转化成了求区间出现次数不小于2的最大数字的ds,此处2取任意常数都能做,具有普适性。
    • 考虑这个2的性质,对每条边有关点求答案\(\rightarrow\)考虑每个点对哪些边有什么贡献,记一个权值出现次数为cnt,若\(cnt > 2\),根据鸽巢原理,随便怎么分都有一棵子树可被记入;若\(cnt = 2\),只有在出现的两个点之间的路径上不能被记入,剩下的都行;若\(cnt = 1\),无论如何都无法被记入。对于树上路径直接上树剖,求得路径的补集即可。code
  • CF1805D A Wide, Wide Graph 考虑优化每个点合并的次数,比较容易想到仅保留最远一次合并。如何证明?经典结论:离树上某个点最远的点在树直径的两个端点中,如果我们考虑这样求出最远点,一开始会先连上直径,然后所有都和直径端点合并,只会向一个大连通块合并,正确性显然。问题在于我场上写了换根dp实现求最远点,这个证明考虑对于点u,在直径端点中和s较远,我们的决策选中了v成为u的最远点,和u到s距离相等,这说明t和v同样构成合法直径,t,v,s一开始就连上了,所以依旧仅有一个大连通块(附加结论,u,v一定经过直径s,t,应该是对的)。code
http://www.hskmm.com/?act=detail&tid=11061

相关文章:

  • 详细介绍:阻塞 IO为什么叫BIO,非阻塞IO为什么叫NIO,异步IO为什么叫AIO
  • Ubuntu系统使用gcc和Makefile编译C程序
  • 构造选记
  • 0133_解释器模式(Interpreter)
  • trick杂记 例题
  • 代码随想录算法训练营第四天 | leetcode 24
  • 网络流 最小割、费用流
  • DP tricks
  • 碎碎念(十七)
  • OpenCV的一些API的使用
  • 2971:抓住那头牛
  • 高效测试的第一步:5个用例设计基础思维模型
  • MFC Button 控件完全指南:从基础到进阶 - 指南
  • Python笔记总结
  • vulnhub靶机:GoldenEye-v1
  • 8465:马走日
  • 性能调优之NUMA调优
  • 深入解析:SpringMVC静态资源与Servlet容器指南
  • CCPC Online 2025 游寄
  • CentOS 7 容器时遇到了 yum update 报错
  • MIT新论文:数据即上限,扩散模型的关键能力来自图像统计规律,而非复杂架构
  • 基于MATLAB的视频动态目标跟踪检测搭建方案
  • U522155 数据生成(小心电脑)
  • 实用指南:OSG中osgFX库
  • 如何将带有线网卡和无线网卡的台式机作为网关/路由器
  • 2025.9.20——1橙
  • 日期
  • 【GAN网络解惑】面向产品的优化:推理裁剪、蒸馏、INT8/FP8 量化,GAN 的真实延迟如何打下来? - 教程
  • 资本与资本主义
  • 202509_NBWS_encoded_csv