2015-2016 ACM-ICPC, NEERC, Northern Subregional Contest
今天遇到了一个挺有意思的算法题目,题目是给定一个有向无环图(DAG),我们要在它上面最多添加k条边,使得这个图依然保持为DAG,同时其最小字典序的拓扑排序结果尽可能大。听起来有点复杂,但我觉得可以一步步来分析。首先,了解DAG和拓扑排序的基本概念。DAG是有向无环图,拓扑排序是对这样的图进行节点排序,使得每个节点都在它所有前驱节点之前。最小字典序的拓扑排序就是尽可能在前面放置大的节点,后面放小的节......