bzoj#P1703. [Usaco2007 Mar]Ranking the Cows 奶牛排名
[Usaco2007 Mar]Ranking the Cows 奶牛排名
题目描述
农夫约翰有 头奶牛,每一头奶牛都有一个确定的独一无二的正整数产奶率。约翰想要让这些奶牛按产奶率从高到低排序。 约翰已经比较了 对奶牛的产奶率,但他发现,他还需要再做一张关于另外 对奶牛的产奶率比较,才能推断出所有奶牛的产奶率排序。请帮他确定 的最小值。
输入格式
第一行包含两个用空格分开的整数 和 。
接下来 行,每行有两个用空格分开的整数 和 ,表示奶牛 的产奶率高于奶牛 。
输出格式
的最小值。
5 5
2 1
1 5
2 3
1 4
3 4
3
样例说明
FJ is comparing cows and has already determined that cow > cow , cow > cow , cow > cow , cow > cow , and cow > cow (where the '>' notation means "produces milk more quickly").
从输入样例中可以发现,约翰已经知道的排名有奶牛 >奶牛 >奶牛 和奶牛 >奶牛 >奶牛 ,奶牛 排名第一。但是他还需要知道奶牛 的名次是否高于奶牛 来确定排名第 的奶牛,假设奶牛 的名次高于奶牛 。接着,他需要知道奶牛 和奶牛 的名次,假设奶牛 的名次高于奶牛 。在此之后,他还需要知道奶牛 的名次是否高于奶牛 。所以,他至少仍需要知道 个关于奶牛的排名。
数据规模与约定
对于 的数据,,,。
题目来源
Gold