稀疏图和只有边权本质相同。
- 只有点权转只有边权：每个点都拆成两个新节点，然后两个新节点间连一条边。
- 只有边权转只有点权：对每条边新建一个点，变成进入该点的一条无权边和离开这个点的无权边、
by yummy @ 2022-11-25 16:01:46
有向无环图可以做到$\Theta(n+m)$吧
by syysongyuyang @ 2022-11-25 16:09:07
@[syysongyuyang](/user/227723) 有向无环图只有边权应当也是 $O(n+m)$。都是拓扑排序。
by wei_xin @ 2022-11-25 16:16:29
@[wei_xin](/user/601360) 正确的
by syysongyuyang @ 2022-11-25 16:18:40
@[yummy](/user/101694) 谢谢
by Taystered @ 2022-11-25 16:18:52
@[syysongyuyang](/user/227723) @[wei_xin](/user/601360) 谢谢
by Taystered @ 2022-11-25 16:19:21