hdoj2647

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=2647
这道题挺有意思,题目意思不再叙述,关键在于拓扑排序的时候要记录各个点的层次,开始没想到怎么做,看了一篇及解题报告才明白。。其实很很简单,只要在进队时看这个顶点是有哪个顶点扩展的,父顶点的层次加1就是该顶点的层次。
思路很简单,但还是WA了,忽略了一点,如果一个顶点层次小于层次最深的顶点,并不能说明该顶点就一定要付大于888的奖金。因为他的后面可能没有约束一个或多个人的奖金应该比他低,这时他和图中层次最深的人的奖金应当相同(都是888)。(注意理解这段,如果不能很好理解,请考虑下该图不连通时的情景)。
怎么办呢?其实也很简单,把有向弧倒过来即可,这时拓排序列是满足:若a的奖金应少于b,则a在b前面。这时候从前往后赋层次值(从0开始),层次值就表示比888大多少了。^_^

hdoj3342

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3342
拓扑排序题,将各位cow看成顶点,师徒关系看成有向弧,如果其中有两个人a、b互为师徒,则a到b必定存在路径,b到a也是如此。这样就形成了环。也就是说,要使关系legal,则必须是有向无环图,用拓排判断。开始的时候在想若是非强连通图如何,呵呵~,其实拓扑排序对于连通也好,非连通也好,都能判环的存在与否。。