位运算的Floyd
题意
给你M个关系,A,B代表第A个数严格大于第B个数,现在这样形成的关系是否有可能存在中位数,可能的话就输出1.
思路
我们需要知道的是由于关系的复杂性很可能存在多个可能的中位数。我们想一下如果这个数字不是中位数的话,那么小于或者大于它的数字一定多余等于n/2个,那么我们应该怎么判断两个数字之间的关系呢,利用Floyd我们就可以求出他们每两点之间的关系。
1 |
|
云腾致雨,露结为霜
位运算的Floyd
给你M个关系,A,B代表第A个数严格大于第B个数,现在这样形成的关系是否有可能存在中位数,可能的话就输出1.
我们需要知道的是由于关系的复杂性很可能存在多个可能的中位数。我们想一下如果这个数字不是中位数的话,那么小于或者大于它的数字一定多余等于n/2个,那么我们应该怎么判断两个数字之间的关系呢,利用Floyd我们就可以求出他们每两点之间的关系。
1 | #include <iostream> |