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

二分图与网络流 Trick

dag 最大独立集(也叫最长反链)

Dilworth 定理:一个 dag 中最大独立集的大小,等于其偏序集的最小不可重链覆盖的大小。

听着很神秘,实际是这样:

偏序集:对于每一个点三元组 \((i, k, j)\),如果原图中有边 \((i, k)\)\((k, j)\),则偏序集中有边 \((i, j)\)
可以 Floyd。

最小不可重链覆盖:用最少条链不重不漏的经过每个点恰好一次。
考虑每个点都是一条链,慢慢合并链,调整。
我们拆点,一排入点,一排出点,构造二分图即可。

知道这个了之后,如果一对点都在最大独立集,则这个点在 dag 的最大独立集上。

P4298 [CTSC2008] 祭祀 - 洛谷

http://www.hskmm.com/?act=detail&tid=28278

相关文章:

  • 10月10号
  • win11 系统如何进行硬盘分区?固态硬盘怎么分区?SSD 固态硬盘分区教程
  • 10/10
  • 数论(未完)
  • 没做完的题
  • 第十一天
  • JavaScriptDay1
  • 淘宝NPM镜像地址https://registry.npm.taobao.org不可用
  • 星星充电一面
  • 6 CF1034 div3 题解
  • 5 ABC413 题解
  • 4 CF 1032 div3 题解
  • 3 ABC411 C ~ E题解
  • 9 ABC408 D~F 题解
  • 8 ABC425 G 题解
  • 智能防御,安全赋能:AI-FOCUS 滤海AI DLP 化解外部 AI 风险
  • IDEA快捷键
  • VS code 中代码补全 自动补全函数括号
  • 优先队列
  • 学习ReAct并使用langgraph实现一个简单的ReAct AI Agent!!
  • abc 408 d~f
  • RMQ与LCA学习笔记
  • mamba-硬件感知算法
  • Java1
  • 完整教程:lua代码解析1
  • 二维数点
  • gitee和github如何修改仓库名并且保持与原远程仓库的连接?(手把手教学) - 实践
  • 2025.10.10总结 - A
  • [20251010]建立完善tpt的prr.sql脚本.txt
  • 第十一篇