http://acm.hdu.edu.cn/showproblem.php?pid=4857

首先我们先按正常的拓扑排序的思路想想:既然要小号在前,那就把原来算法中的queue<int>改成priority_queue<int, vector<int>, greater<int> >
这样对吗?
看这样一组数据:

1
5 3
3 2
4 1
5 1

3在2前面,4在1前面,5在1前面。
按我们的算法,顺序是3-2-4-5-1,但题目说了要让1要尽量在前,此时4-5-1-3-2的安排才是符合题意的。

所以必须从1开始,逆着有向边找到一条尽量短的路线,有多条一样短的路线时还必须让路线上的数尽量小。
所以我们要反向建图。

这样遍历时,还必须尽量让1在后面,所以我们用priority_queue<int>,最后逆着输出。

然后就是模板了,代码就不贴了。

Comments

comments powered by Disqus