优化建图总结

这些方法可以用于最短路,网络流,连通性等问题。

对于区间到区间/点的连边,直接上线段树就行了,这个很简单

对于点到区间/子矩阵的连边(最短路问题),还可以用线段树/KD树维护dis数组,进行区间和某数取min的操作。

对于序列的某个前/后缀的连边,可以直接把这个序列按顺序连边……这个也很简单。

对于树上的连边,有2种方式:

  1. 树链剖分,(O(n))点数,(O(nlog^2n))边数。
  2. 倍增,(O(nlogn))点数,(O(nlogn))边数。

对于二维偏序的连边,对其中一维排序,并使用主席树连边。

原文地址:https://www.cnblogs.com/lnzwz/p/13435963.html