题目详情题解（0）讨论（0）提交记录（0）

AT_arc093_c.[ARC093E] Bichrome Spanning Tree

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个包含 NN 个顶点和 MM 条边的带权无向图。第 ii 条边连接顶点 UiU_i 和顶点 ViV_i，权值为 WiW_i。此外，给定一个整数 XX。

请计算有多少种方法可以将该图的每一条边涂成白色或黑色，使得满足以下条件，并将答案对 109+710^9+7 取模：

  • 存在一棵同时包含白色边和黑色边的生成树，并且所有满足条件的生成树中，权值最小的那一棵的权值恰好为 XX。

这里，生成树的权值指的是该生成树所包含的所有边的权值之和。

输入格式

输入以如下格式从标准输入读入：

NN MM XX
U1U_1 V1V_1 W1W_1
U2U_2 V2V_2 W2W_2
⋮\vdots
UMU_M VMV_M WMW_M

输出格式

输出答案。

输入输出样例

  • 输入#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

  • 输入#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≤1,0001 \leq N \leq 1,000
  • 1≤M≤2,0001 \leq M \leq 2,000
  • 1≤Ui,Vi≤N1 \leq U_i, V_i \leq N（1≤i≤M1 \leq i \leq M）
  • 1≤Wi≤1091 \leq W_i \leq 10^9（1≤i≤M1 \leq i \leq M）
  • 当 i≠ji \neq j 时，(Ui,Vi)≠(Uj,Vj)(U_i, V_i) \neq (U_j, V_j) 且 (Ui,Vi)≠(Vj,Uj)(U_i, V_i) \neq (V_j, U_j)
  • Ui≠ViU_i \neq V_i（1≤i≤M1 \leq i \leq M）
  • 给定的图是连通的。
  • 1≤X≤10121 \leq X \leq 10^{12}
  • 所有输入值均为整数。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页