背景

给定一张带负权边的有向无环图(DAG),$N$ 个点,$M$ 条边,求源点到各点的最短路。

分析

因为有负权边,无法用 dijkstra 直接求最短路。

用 SPFA 又容易被出题人卡成傻子

考虑到是 DAG,可以使用拓扑排序在 $O\left( N+M \right)$ 时间范围内求出最短路。

阅读全文 »

已经是22年了捏。

!!!🏮新年好🏮!!!

Dumby_cat 隆重推出 Dumblog 新年款!!!(其实就是变红了。。。)

总之,祝各位来访者新年快乐!!!

并查集是甚么

并查集(Disjoint-set data structure),直译为 “不交集数据结构”,顾名思义,它是种数据结构。并且,它是种用来处理 不交集(不相交集合)的合并和查询问题 的数据结构。
并查集维护的是元素之间的关系

阅读全文 »