TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3986
  • Problem
  • P3986说谎的奶牛
    Limits : Time Limit : - MS   Memory Limit : 165536 KB
    Judgment Tips : 1s
    Description

    兽群中总是有一些麻烦制造者.约翰知道他的N(1≤N≤100)头奶牛中可能有一头总是说谎,其他的总是说真话.他想快速的找出这个麻烦制造者.为了实现这个目标,他一个一个的问这些奶牛Q(1≤Q≤1000)个关于它们吃草的简单问题(虽然大多数奶牛是诚实的但它们依旧很笨只能懂得一些关于食物的话题).

    他将这些问题用以下的格式写了下来:

    牛4说:牛5比牛10吃得多

    牛6说:牛10比牛7吃得多

    牛3说:牛2比牛6吃得多

    牛1说:牛7比牛5吃得多

    从这个例子中不难看出说谎的奶牛只有可能是4,6,1.你的任务是确定可能说谎的奶牛的个

    数.可能说谎的奶牛是指如果这头奶牛说谎则输入数据中不存在矛盾.

    Input Format

    第1行:两个用空格分开的整数N和Q.

    第2到Q+1:每一行描述一个问题,由3个用空格隔开的整数A,B,C表示,意思是A说B牛吃的比C牛多.一头奶牛可能回答多次.

    Output Format

    仅一行一个整数即可能说谎的奶牛的头数.

    Sample Input 1

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

    Sample Output 1

    2

    Sample Input 2

    10 9
    3 1 2
    3 2 3
    4 3 4
    1 4 5
    4 5 1
    2 7 6
    5 8 7
    5 6 9
    4 10 9

    Sample Output 2

    3

    Hint

    样例说明
    3头奶牛给出了4个回答.奶牛1说3>1,3>2,奶牛2说2>1,奶牛3说1>2.当然“>”的意思是“吃得多”. 显然,2号和3号的话是矛盾的.它们都有可


    Source  [Usaco2004 Mar]