【HNOI2015】菜肴制作

HNOI的题目都太鬼了 我只会做这一道题面正常的

题目大意就是,给你一张拓扑图,让你找一条拓扑序,使得1尽量在前面,在此前提上把2尽量放前面,在此前提上把3尽量放前面……

显然是个拓扑排序,然而直接来肯定不行,得对原图的反图(把所有边反过来)进行拓扑排序,尽量先选大的,最后反向输出结果。

证明怎么证的去了。。不记得了==

哦想起来了XD

对于每个数,以1为例:要使1最靠前,就要先把能放到1后面的全部放到1后面,那么在反向拓扑时,会一直找到只有1的入度为0的那一刻才选1。对于每个数,则是一直找到没有比它更大的数入度为0才选它。

说点什么

您将是第一位评论人!

提醒
wpDiscuz