POJ3660传递闭包
传递闭包
传递闭包一般用来解决一类具有传递性的问题。
定义:在交际网络中,给定若干个元素和若干对二元关系,且这些关系具有传递性,通过这些传递性推导出尽量多的元素之间的关系的问题叫做传递闭包。
也就是用已知条件来推出其他所有的可知条件。数独应该就是使用了传递闭包的一个例子。再比如,A>B
,B>C
,通过传递闭包,我们就可以得到A>C
。
将传递闭包问题转化为图论问题。
把元素变成一个点,有关系就连一条边。
最后用Floyd
算法解决两点之间的联通关系。
题目大意:已知一些人的绝对实力关系,让你推出,最后有多少人的绝对实力排名是已知的。
这就是经典的Floyd
传递闭包。
不多说了 看题目和代码:
1 | /* |