TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • 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