TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P5771
  • Problem
  • P5771* 红绿生成树
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 1s,256M
    Description

    何老板给你一个有N个点和M条边构成的无向图。
    每条边都有一定的长度。一开始所有边都没有被涂颜色,何老板准备了红绿两种颜料,你可以将边涂成红色或绿色。
    何老板要你将图中每条边都涂上颜色。但要求该图中存在既有红边又有绿边的生成树。且这些包含红绿边的生成树中,边长总和最小的一棵恰好为X。
    何老板问,有多少种满足上述要求的涂色方案?mod $10^9+7$后再输出。

    Input Format

    第一行,两个整数N和M
    第二行,一个整数X
    接下来M行,每行三个整数,U,V,W表示有一条连接点U和V,且长度为W的无向边

    Output Format

    一个整数,表示方案数

    Sample Input 1

    3 3
    2
    1 2 1
    2 3 1
    3 1 1

    Sample Output 1

    6

    Sample Input 2

    3 3
    3
    1 2 1
    2 3 1
    3 1 2

    Sample Output 2

    2

    样例解释:
    合法的涂色方案有:
    1.(1,2,红)(2,3,红)(3,1,绿)  
    2.(1,2,绿)(2,3,绿)(3,1,红)  

    其他方案可以找出边长总和比3更小的红绿生成树,所以不合法

    Sample Input 3

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

    Sample Output 3

    0

    Sample Input 4

    8 10
    49
    4 6 10
    8 4 11
    5 8 9
    1 8 10
    3 8 128773450
    7 8 10
    4 2 4
    3 4 1
    3 1 13
    5 2 2

    Sample Output 4

    4

    Hint

    $1≤N≤1000$
    $1≤M≤2000$
    $1≤W≤10^{9}$
    $1≤X≤10^{12}$
    给出的图是连通的,且不含重边和自环


    Source  ARC093E