#P3373. [Usaco2004 Mar]Lying Livestock 说谎的牲畜
[Usaco2004 Mar]Lying Livestock 说谎的牲畜
[USACO 2004 Mar] Lying Livestock 说谎的牲畜
题目描述
约翰有 头奶牛,编号为 到 。他想找出唯一一头总是说谎的奶牛,其余奶牛总是说真话。他询问她们吃草量的比较关系,然后记录了 条回答。
例如, 号说 号比 号吃得多, 号说 号比 号吃得多, 号说 号比 号吃得多, 号说 号比 号吃得多。根据这四句话,只有 号奶牛可能是说谎者。
如果能给每头奶牛指定一个吃草量,使某头奶牛的所有回答都为假、其他奶牛的所有回答都为真,则该奶牛是可能的说谎者。两头奶牛可以吃得一样多。求可能的说谎者数量。
输入格式
从标准输入读入。第一行是两个整数 。接下来 行,每行三个整数 ,表示奶牛 说奶牛 比奶牛 吃得多。同一头奶牛可以回答多次。
输出格式
向标准输出输出一行一个整数,表示可能的说谎者数量。
3 4
3 1 2
1 3 1
1 3 2
2 2 1
2
样例解释
奶牛 和 分别说 和 ,两者不能同时为真。假定其中一头说谎,都可以让其他所有回答成立。若假定 号说谎, 号与 号的话就必须同时为真,因此不可能。
数据范围与约定
,。奶牛编号均在 到 之间。