HNOI2015 菜肴制作贪心的证明

发现如果要让标号小的点尽量靠前,则它的前驱选完后紧接着就选这个点。

考虑这个贪心:建反图,每次选全局最小点(初始是1),把非这个最小点的后继(间接的也算)和1号点从图中删除,接着选还留下的点中点权最小的,把非这个最小点的后继(间接的也算)和当前点从图中删除,以此类推直到图只有1个点,则把现在这个点插入到答案序列的末尾,把原图(即输入的图)删掉这个点,然后继续进行此算法,正确性显然。

但是1e5的数据范围不允许我们使用这个贪心。实际上,当前全局最小点的前驱选完后紧接着就选这个点,所以这个点和它的后继肯定占用了答案序列的一段前缀。把这个前缀从答案序列和图中删除,继续执行这个过程直到只有1个点。则未被删除的最后一个点肯定是目前权值最大且没有出度的点。这个点肯定在答案序列的末尾,把这个点删除,继续执行这个过程,且把每个得到的点依次插入在答案序列的开头,直到原图为空。这个过程实际上就是使用大根堆进行的拓扑排序。

这个结论在agc001f上也有运用

原文地址:https://www.cnblogs.com/cszmc2004/p/12576542.html