洛谷秋令营Day4-进阶图论

拓扑排序

P7113，注意数据范围别爆了，long long 也存不下，需要用 __int128

P7473，每个点需要预处理四个方向重力切换到哪儿，似乎考虑从某个点如何能走到这两个点更好，反过来建图做。注意到障碍物个数不多，只有这个障碍物的四周，以及边界是可能切换到的点，所以有用的点的个数其实只有 $O(n + m)$个。这样，我们再建一个超级源点（然后呢？）

P7077，题还没看明白，暂时先跳过这个题。

最小生成树

P4180，套路题，枚举不在 MST 上的边，考虑加上这条边，得到一个环，再删掉一条边。

CF1550F，

Kruskal 重构树，

P4768，如果不是强制在线，怎么做？可以预处理 1 的最短路，并按照 p 从大到小对询问排序，这样可用的边只会越来越多，使用并查集维护连通性，并维护所在集合里 d[i] 最小的值，每次把 v 所在集合里的最小值回答出来就好了，非常简单。如果强制在线，按照海拔从大到小排序边，建 kruskal 重构树，则考虑询问 (v, p) 时，找到 v 的最浅的一个祖先 anc，使得这个祖先的海拔 > p，则 anc 所在子树里所有的点就是 v 只走海拔 > p 的边能走到的点，只要维护这棵子树里面的距离最小值就好了，这个是可以预处理出来的。

最短路

差分约束

连通性

强连通

2-SAT 问题

点双与边双

杂项

欧拉回路

数据结构优化建图，减少边的数量