TouchStone
  Please Login
Login Sign Up
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P6574
  • Problem
  • P6574纸牌杀游戏
    Limits : Time Limit : 2000 MS   Memory Limit : 1048576 KB
    Description

    南渝中学同学们之间流行一个纸牌杀的游戏,游戏开始有$N$张扑克牌$A_1,A_2,\cdots,A_N$,并且面都朝下,每张上写着1或者2,玩家的任务就是准确无误猜出所有扑克牌的数字,即为过关。当然游戏会给玩家提供$M$条信息。信息的形式如下:$A_{X_i}+A_{Y_i}+Z_i$的结果是偶数$(i=1,2,\cdots,M)$。不过,你也可以选择充值买道具,道具1元1个,道具一次只能查看一张牌的数字,用后即废。请问玩这局游戏至少需要充值多少才能过关?一些限制条件如下:

    1. 输入的值都是整数
    2. $2 \leq N \leq 10^5$
    3. $1 \leq M \leq 10^5$
    4. $1 \leq X_i < Y_i \leq N$
    5. $1 \leq Z_i \leq 100$
    6. $(X_i,Y_i)$这对数据不会重复出现
    7. 输入都是有效的,即一定可以找到一组数字$A_1,A_2,\cdot,A_N$满足条件。
    Input Format

    第一行,两个整数$N$和$M$。接下来$M$行,每行3个整数$X_i$ \(Y_i\) $Z_i$表示信息。格式如下:
    \(N\)   \(M\)
    \(X_1\)   \(Y_1\)  \(Z_1\)
    \(X_2\)   \(Y_2\)  \(Z_2\)
    \(\vdots\)
    \(X_M\)   \(Y_M\)  \(Z_M\)

    Output Format

    输出一个整数表示至少需要充多少钱。

    Sample Input 1

    3 1
    1 2 1

    Sample Output 1

    2

    Sample Input 2

    6 5
    1 2 1
    2 3 2
    1 3 3
    4 5 4
    5 6 5

    Sample Output 2

    2