拓扑排序

感觉自己拓扑学的稀烂，感觉不是很熟练，还是要多练。

P4316 绿豆蛙的归宿

首先题目给出的是 DAG，方便我们用拓扑来求解。本题是求期望，那么我们正着求不太好求因此我们倒着求解，设 $f_u$ 表示从 $u$ 走到 $n$，$f_n=0$，答案就是 $f_1$。因此我们建反图，从 $n$ 倒着拓扑就行了。

P1983 [NOIP2013 普及组] 车站分级

因为火车停留的都是比它级别高的车站，因此没听的都是级别比它小的，求最高级别至少是多少。我们把级别高的向级别低的连边，然后跑拓扑求出层数即可。

[P7113 [NOIP2020] 排水系统](P7113 [NOIP2020] 排水系统)

直接拓扑排序，注意高精。不过似乎 long double 可以应对。

最短路

最短路计数

P1606 [USACO07FEB]Lilypad Pond G

我们根据原图建边，把到荷花的建 $0$ 权边，到水的建 $1$ 权边。然后跑最短路和最短路计数就行了……吗？我们发现结果和答案有些出入，我们发现因为优先队列的存在，$0$ 权边的存在会使得更新 $u$ 的时候可能路径数没有统计完全。因此我们把所有荷花当作一个连通块，这样就避免想荷花连边了。

最短路 + 最小生成树

CF196E Opening Portals

首先考虑这个传送门可以互相传送的性质代表什么，其实相当于很多没必要的路都不必走了，相当于只要求传送门间的最小生成树再加上 $1$ 号点到最近的传送门就行了。但发现瓶颈是我们不可能求多源最短路，因此必须要优化。这就用到了一个技巧，我们先把所有传送门放进优先队列，跑一边 dijkstra，求出离自己最近的点。然后 $u,v$ 间连边，$u$ 最近的是 $u'$，$v$ 最近的是 $v'$，那么它们的边权就是原边权加上 $dis_{u',u}$ 和 $dis_{v',v}$。

其他

P3645 [APIO2015]雅加达的摩天楼

无权图最短路，直接用 bfs 就行了。用 set 判重会超时，因此用 bitset 来优化。

图的连通性

P3225 [HNOI2012]矿场搭建

坍塌就是删除一个点，删的不是割点只用放一个就行了，若是割点的话两边的连通块都要放一个，接下来还要再分类。

若是一条链：那么直接两个端点都放就行了。

若是一个环：那么删除一个点不会影响什么，但是还要考虑删取撤离点的情况，因此至少放两个点，方案为 $C_{n}^2$。

其他情况：删除割点后会形成多个连通块。每个连通块都要放一个，同时还要考虑删除撤离点的情况。如果有两个及以上的割点，那么可以直接到达其他连通块。

P2403 [SDOI2010]所驼门王的宝藏

tarjan $+$ 拓扑。

本题就是建边有些困难，我们把横天门和纵寰门和横纵的宫室都建边，然后跑 tarjan 求强连通分量，然后缩点拓扑跑 dp，设 $f_i$ 表示到前 $i$ 个点经过的最多宫室数，$f_{v}=\max(f_v,f_u+val_v)$。