搜索结果
查询Tags标签： 反链，共有 6条记录-
有负权图上的最短路算法 (Goldberg, 1995)
最近听说有了一个有负权图上的 \(O(m\log^8 m \log w)\) 算法, 感觉非常厉害, 于是觉得先来研读一个早些的工作. 如果有可能的话再尝试研读新的算法! 我们知道, OI 中常用的在负权图上的 Bellman–Ford 算法可以在 \(O(nm)\) 时间内计算一个有负权图的单源最短路径, 或者确…
2022/4/9 22:19:48 人评论 次浏览 -
关于最小路径覆盖
首先最小路径覆盖问题的前提是 \(DAG\) ，并且有两种，一种是最小相交路径覆盖问题（一个点可以在多条路径中）又名最小边覆盖，另一种是最小不相交路径覆盖问题（一个点只能被覆盖在一条路径中）又名最小点覆盖。 最小不相交路径覆盖问题 这个东西的解的数量我不知道有没…
2021/7/20 23:07:07 人评论 次浏览 -
关于最小路径覆盖
首先最小路径覆盖问题的前提是 \(DAG\) ，并且有两种，一种是最小相交路径覆盖问题（一个点可以在多条路径中）又名最小边覆盖，另一种是最小不相交路径覆盖问题（一个点只能被覆盖在一条路径中）又名最小点覆盖。 最小不相交路径覆盖问题 这个东西的解的数量我不知道有没…
2021/7/20 23:07:07 人评论 次浏览 -
dilworth 定理
定义集合 \(\mathbb{S}\) 上的偏序集 \((\mathbb{S}, \le)\)，其中 \(\le\) 表示一种关系（不一定就是不大于），满足如下性质：自反性 \(:a \le a\)。反对称性 \(:a \le b, b \le a \Longleftrightarrow a = b\)传递性 \(:a \le b, b \le c \Longrightarrow a \le c\)定义…
2021/7/7 23:06:31 人评论 次浏览 -
[CTSC2008]祭祀（二分图+网络流）
题目：洛谷P4298 题目描述： 给定一个\(n\)个点，\(m\)条边的有向无环图（\(DAG\)），求最多能选多少个点使得它们两两之间不能到达，并且要求你构造出一种方案，且判断每个点是否有可能被选出 \(n \leq 100\)，\(m \leq 1000\) 蒟蒻题解： 在一个\(DAG\)中，它的最长反链…
2021/5/12 10:28:33 人评论 次浏览 -
[计蒜客]A1542 The Maximum Unreachable Node Set
题目链接：The Maximum Unreachable Node Set 题目大意： 给定一个偏序集，求最长反链大小。 反链的定义是：链上的任意两点互不可达。趁机补一补图论的东西。 这道题是道板子题，不过没学过基本上写不出来吧。 首先有两个前置技能： 1.求偏序集上最小不相交链覆盖数 每个…
2021/5/1 12:55:08 人评论 次浏览
