搜索结果
查询Tags标签： 出边，共有 11条记录-
[模板] BEST 定理
一、题目 点此看题 二、解法 这篇博客主要记录我的感性理解，相信能帮助你直观地理解 \(\tt BEST\) 定理。 首先对于一条欧拉路径，我们考虑保留每个点的最后一条出边。可以证明出边一定构成一棵内向树，我们只需要证明不会构成环，而如果构成环，考虑走完环的最后一条出边…
2022/3/8 23:47:01 人评论 次浏览 -
C++解决最短路径问题
很多概念性问题笔者都没有理解理解清楚，所以很多基本上全篇都有待完善.... 先说多源最短路径算法 1.floyd算法（暴力n3）： （Floyd当然也能解决单源最短了，它就是多个单源最短的集合。） 核心代码只有三行，文字描述就是：假设n个点，点与点间有m条边（无独立的点），我…
2021/11/12 11:10:39 人评论 次浏览 -
C++解决最短路径问题
很多概念性问题笔者都没有理解理解清楚，所以很多基本上全篇都有待完善.... 先说多源最短路径算法 1.floyd算法（暴力n3）： （Floyd当然也能解决单源最短了，它就是多个单源最短的集合。） 核心代码只有三行，文字描述就是：假设n个点，点与点间有m条边（无独立的点），我…
2021/11/12 11:10:39 人评论 次浏览 -
【题解】[CCO2021] Travelling Merchant
先口胡一个，明天再来补代码（ 先考虑 \(-1\) 的情况，显然没有出边的点是 \(-1\)，将这样的点和对应的边删掉，直到每个点都有出边。显然被删掉的点都是 \(-1\)，其余的点都不是 \(-1\)。 对于剩下的边，显然 \(r_i\) 最大的边如果走了，那么其他的边随便走，所以对应的 …
2021/8/24 23:36:33 人评论 次浏览 -
【题解】[CCO2021] Travelling Merchant
先口胡一个，明天再来补代码（ 先考虑 \(-1\) 的情况，显然没有出边的点是 \(-1\)，将这样的点和对应的边删掉，直到每个点都有出边。显然被删掉的点都是 \(-1\)，其余的点都不是 \(-1\)。 对于剩下的边，显然 \(r_i\) 最大的边如果走了，那么其他的边随便走，所以对应的 …
2021/8/24 23:36:33 人评论 次浏览 -
线性代数相关算法小记
高斯消元 高斯消元是对矩阵行化简的算法，可以化成阶梯型或者简化阶梯型。《线性代数及其应用》给出的步骤如下：选取最左边的非零列； 在该列中任意选取一个非零元素，通过对换变换将该行移到最上面； 通过倍加变换将下面的行的该列元素全部变成 \(0\)； 暂时不管该行（即…
2021/8/19 22:05:42 人评论 次浏览 -
线性代数相关算法小记
高斯消元 高斯消元是对矩阵行化简的算法，可以化成阶梯型或者简化阶梯型。《线性代数及其应用》给出的步骤如下：选取最左边的非零列； 在该列中任意选取一个非零元素，通过对换变换将该行移到最上面； 通过倍加变换将下面的行的该列元素全部变成 \(0\)； 暂时不管该行（即…
2021/8/19 22:05:42 人评论 次浏览 -
题解 竞赛图
传送门 考试的时候想到了一个应该有60pts的 \(O(2^nn^2T)\) 但是 \(n^2\) 只是枚举边的状压 然后挂成40pts，从中午12点拍到晚上5点半没拍出来 记得哪天去要下这题数据 考试的时候如何发现这些奇奇怪怪的性质啊…… 正解需要 \(O(2^nT)\) 才能过 所以枚举点集跑check一定会…
2021/8/15 6:35:42 人评论 次浏览 -
题解 竞赛图
传送门 考试的时候想到了一个应该有60pts的 \(O(2^nn^2T)\) 但是 \(n^2\) 只是枚举边的状压 然后挂成40pts，从中午12点拍到晚上5点半没拍出来 记得哪天去要下这题数据 考试的时候如何发现这些奇奇怪怪的性质啊…… 正解需要 \(O(2^nT)\) 才能过 所以枚举点集跑check一定会…
2021/8/15 6:35:42 人评论 次浏览 -
弗洛伊德判环，找环起点，找环长的算法
弗洛伊德判环，找环起点，找环长的算法 目录弗洛伊德判环，找环起点，找环长的算法有这样一种问题……弗洛伊德判环 有这样一种问题…… 对于一种特殊但是常见的有向图：每个点都有一条出边（出度为0）。我们想要掌握它的结构，怎么办呢？很容易发现，这样的图一定是这样的…
2021/8/6 1:35:48 人评论 次浏览 -
弗洛伊德判环，找环起点，找环长的算法
弗洛伊德判环，找环起点，找环长的算法 目录弗洛伊德判环，找环起点，找环长的算法有这样一种问题……弗洛伊德判环 有这样一种问题…… 对于一种特殊但是常见的有向图：每个点都有一条出边（出度为0）。我们想要掌握它的结构，怎么办呢？很容易发现，这样的图一定是这样的…
2021/8/6 1:35:48 人评论 次浏览
