#P3373. [Usaco2004 Mar]Lying Livestock 说谎的牲畜

    ID: 2562 传统题 1000ms 512MiB 尝试: 163 已通过: 54 难度: 5 上传者: 标签>难度分类普及+/提高-枚举与搜索暴力枚举图论差分约束Bellman–Ford负环检测超级源汇CF1700Orange

[Usaco2004 Mar]Lying Livestock 说谎的牲畜

[USACO 2004 Mar] Lying Livestock 说谎的牲畜

题目描述

约翰有 NN 头奶牛,编号为 11 到 NN。他想找出唯一一头总是说谎的奶牛,其余奶牛总是说真话。他询问她们吃草量的比较关系,然后记录了 QQ 条回答。

例如,44 号说 55 号比 1010 号吃得多,66 号说 1010 号比 77 号吃得多,33 号说 22 号比 66 号吃得多,11 号说 77 号比 55 号吃得多。根据这四句话,只有 1,4,61,4,6 号奶牛可能是说谎者。

如果能给每头奶牛指定一个吃草量,使某头奶牛的所有回答都为假、其他奶牛的所有回答都为真,则该奶牛是可能的说谎者。两头奶牛可以吃得一样多。求可能的说谎者数量。

输入格式

从标准输入读入。第一行是两个整数 N,QN,Q。接下来 QQ 行,每行三个整数 A,B,CA,B,C,表示奶牛 AA 说奶牛 BB 比奶牛 CC 吃得多。同一头奶牛可以回答多次。

输出格式

向标准输出输出一行一个整数,表示可能的说谎者数量。

3 4
3 1 2
1 3 1
1 3 2
2 2 1
2

样例解释

奶牛 22 和 33 分别说 2>12>1 和 1>21>2,两者不能同时为真。假定其中一头说谎,都可以让其他所有回答成立。若假定 11 号说谎,22 号与 33 号的话就必须同时为真,因此不可能。

数据范围与约定

1≤N≤1001\le N\le 100,1≤Q≤1 0001\le Q\le 1\,000。奶牛编号均在 11 到 NN 之间。