几道拓扑排序题的分析

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-28 21:44:51

P4316 绿豆蛙的归宿

题意比较简单：走到每一条边的概率是起点的出度分之一，保证图联通无环，求路径总长度的期望。

这是一个简单的图上拓扑 DP。只需要设 $f(v)$ 代表走到点 $v$ 的概率，于是 $f(v) = \dfrac {f(u)}{d^+(u)}$。于是明显，走到边 $(u, v)$ 的概率就是 $\dfrac {f(u)}{d^+(u)}$。

由于图是联通且无环的，我们统计总和即可。

题意就是：给定了 $a_i$ 与 $b_i$ 之间的关系，求最小可能的 $a$ 与 $b$ 序列。

利用拓扑排序解决问题的关键在于找出顶点之间的关系与限制，然后用拓扑排序取得一个可行解。在这个问题中，很明显，限制就是元素之间的大小关系。

但是需要处理相等的情况。很明显，可以用一个并查集将相等的元素合并起来，因为无论怎么样，这些数的最终取值都是相等的。

之后一遍拓扑即可。

我们可以想到：两量方向向外的车，一定无关紧要；同理，两辆命中注定的车，一定共同指向内端。再考虑方向：根据上面的方案，不管两辆车是无关紧要还是命中注定，它们方向都相反。我们可以简单的设 $1$ 号车的方向向左，然后染色即可。

之后我们建图。其实可以用原图来删边，省空间，不过逆向思维不好想。

如果没有限制顺序的要求，简简单单拓扑就行了。但是这个限制没有看起来那么简单：要求的是编号小的尽可能往前，但这并不是说字典序尽可能小。考虑 $2314$ 和 $3124$，前者的字典序更小，但后者才是题中说的更优的。

那这怎么处理？把它翻转过来：我们要求小元素尽量靠前，反过来就是小元素尽量靠后，也就是大元素尽量靠前，这实际上就是说字典序最大。那么原来的要求反过来是什么？是说编号大的尽可能往后，是句废话，没法转化。

所以我们要做的就是建反图，用优先队列让大编号点尽可能往前，然后取逆序列。

题意（翻译）极其简洁。既然要 “最大值最小”，很明显二分。于是将最优化转化成可行性判定：是否能通过改变边权小于等于 $k$ 的边来使图变为有向无环图。

我们知道：如果不限制边权，那么一定能将一个图转化为无环图。方法如下：我们找到图中入度最小的点，把它的所有入边改成出边，这样就能让它脱环。将它删除后，对剩余图进行同样的操作。

于是我们知道：只要是由边权大于等于 $k$ 的边组成的图无环，我们就一定能仅仅通过改变边权小于 $k$ 的边，将这个图转化为无环的。判断有环是简单的，可以用拓扑，也可以用 DFS。

最后的问题就是怎么求方案。实际上也简单。我们对由边权大于等于 $k$ 的边组成的子图进行拓扑排序，得到每个点的拓扑序。然后对剩下的每一条边，使起点的拓扑序小于终点，否则改变方向。注意我们并不求改变方向的最少次数。

拓扑排序有两种题：图上 DP 与求限制方案。对于前者，实际上动态规划转移的过程就是在 DAG 上遍历。点就是状态，而边就是转移。我们设出点代表的状态，然后来找与此相关的边的转移。

对于后者，重要的是找到边的方向以及权值代表的实际意义。这需要我们理解拓扑的原理：起点在拓扑序中，一定在终点之前。通过这个原理，我们就能排出方案。