Luogu7054 [NWRRC2015]Graph

题意：给定一张 点 条边的有向无环图，你可以至多添加 条有向边，使得这仍然是一个有向无环图，使得字典序最小的拓扑序的字典序尽量大。

求出这个最大的最小拓扑序，并构造一种加边方案。

，时限 。

---

• 性质：记最终的拓扑序为 ，则加入的边一定可以都形如 。

  证明：将每个加入的弱连通块换成一条链，显然不会增多边数，且不会减弱限制。

根据这条性质，如果我们得到了 ，那么只需要知道那些点有（新）入度，就可以得到需要连的边。

下面考虑构造：字典序贪心。

确定某一位拓扑序 时，考虑目前所有 入度点中最小的 。

• ① 若 为唯一的 入度点或 ，那么我们不得不将 弹出（并删除其出边），作为这一位拓扑序。

• ② 若 并不是唯一的 入度点且 ，那么我们可以给 加一条入边。

  我们暂不考虑入边的起点是谁。

如上流程有个问题，将 弹出并删除其出边时，我们不能确定 是否是某个新边的起点。

但我们不能从“起点”出发考虑，那样太麻烦，转而从“终点”出发考虑。

我们引入“次 入度点”的概念，指这些点原本为 入度点，但因为加入了新边而变为 入度点。即在 ② 中产生的点。

次 入度点会影响“ 为唯一的 入度点”这一判断。若存在次 入度点 ，其入边起点已经被删，则目前就是一个 度点。

考虑最大的次 入度点 ，若有 ，则通过将 设置为 （只是方案存在性证明，不必真的设置。不难发现这也符合前面的性质），可以使得 在此时恰好变为真·“ 入度点”。

这样我们就能放心地给 加边了。

用小根堆维护“ 入度点”，大根堆维护“次 入度点”即可。复杂度为 。