标签:图论

6 篇文章

Luogu P1983 – 拓扑排序
PROBLEM https://www.luogu.org/problemnew/show/P1983 ANALYSIS STL真的降智 做题之前被周围的人乱说一通更降智 题目大意: 构建低优先级车站指向高优先级车站的单向边,找关键路径。 跑一边拓扑排序就可以了。 使用set的时间约为不使用set时间的13-14倍,空间为5.5倍。也可能是我用的方…
Luogu P1339 – 单源最短路
PROBLEM https://www.luogu.org/problemnew/show/P1339 ANALYSIS 裸题 ,保存模板 时间复杂度: SPFA O(k*E)  , k 为每个节点进入队列的次数,一般小于等于2,最坏情况为O(V*E) Dijkstra(Heap) O(2*E+V*lgV) Dijkstra(Ordinary) O…
Luogu P2921 – 图的遍历
PROBLEM https://www.luogu.org/problemnew/show/P2921 ANALYSIS 寻找从每个点出发到访问到已访问节点(将环封闭)用的时间。 起初自己的想到解法应该和 [lip id=893] 差不多,然而在原先题目的思路去思考这个问题有点受限。   一种正确的做法: 从所有点开始,尝试对节点染色。 …
Luogu P1330 – 图的遍历
PROBLEM https://www.luogu.org/problemnew/show/P1330 ANALYSIS 用不相邻的[crayon-600c228b25975762410103-i/] 的点,切断所有的边。不存在则输出[crayon-600c228b2597b630399681-i/] 。 有点意思的一个题。直接思考可能比较困难,转…
Luogu P2661 – 并查集
PROBLEM https://www.luogu.org/problemnew/show/P2661 ANALYSIS 找到有向图中最小的环。n个点,n条边,n<2*10^5。 SOLUTION 首先是两种弱智模拟做法,STL真的降智。 TLE, 80 [crayon-600c228b25bd7035102117/] TLE, 80 [cr…
Luogu P1341 – 欧拉路径
PROBLEM https://www.luogu.org/problemnew/show/P1341 ANALYSIS 找到无向图中字典序最小的欧拉路径(不一定是回路),不存在则输出[crayon-600c228b25e5a107309176-i/] . 起初考虑复杂了,写了一个没脑子的暴搜。 一笔画问题,如果有奇数入度节点,若数量不为2,则构不…