TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P5771
  • 問題
  • P5771* 红绿生成树
    制限 : 時間制限 : - MS   メモリ制限 : - KB
    審判説明 : 1s,256M
    問題説明

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

    入力形式

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

    出力形式

    一个整数,表示方案数

    サンプル入力 1

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

    サンプル出力 1

    6

    サンプル入力 2

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

    サンプル出力 2

    2

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

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

    サンプル入力 3

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

    サンプル出力 3

    0

    サンプル入力 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

    サンプル出力 4

    4

    ヒント

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


    ソース  ARC093E