poj 3660 Cow Contest (floyd,传递闭包)

2015年12月17日 0 作者 CrazyKK

http://poj.org/problem?id=3660
题意:给定n个奶牛,m个奶牛的关系,a,b表示a比b强…问能确定多少个奶牛的排名。
思路:最重要的一点是。。能确定奶牛i的排名的条件是。。知道奶牛i和其他n-1个奶牛的关系。。不管是能打败奶牛i也好。。会被奶牛i打败也好。。只要不是不确定就行。。所以我们跑一遍floyd做传递闭包。得到任何两个点之间的联系。然后对于每一个点。看其他n-1个点是否和他有关系。