Moorio Kart

题目描述

贝茜和农夫约翰喜欢进行山羊卡丁车比赛。这个想法与其他人喜欢的 Go-Kart 赛车非常相似，只不过卡丁车由山羊拉动，赛道由附近的农田构成。农田由 $N$ 个草地和 $M$ 条道路组成，每条道路连接一对草地。\n\n贝茜想用附近的农场来设计一条赛道。一个农场是由两个或以上草地组成的子集，在其中任意一个草地都能沿着一条唯一的道路序列到达任意其他草地。\n\n附近的农田可能包含多个农场。假设共有 $K$ 个农场。贝茜希望通过添加 $K$ 条长度为 $X$ 的道路，把所有 $K$ 个农场连接起来，形成一条山羊卡丁车的环路。每个农场应当恰好被访问一次，并且在每个农场内部至少要行驶一条道路。\n\n为了让赛道对赛车手更有趣，赛道的总长度至少应为 $Y$。贝茜想知道：在所有这样的“有趣”赛道中，赛道总长度的总和是多少。若两条赛道在（添加农场间道路后）存在一对草地在一条赛道中相邻但在另一条赛道中不相邻，则认为这两条赛道不同。请注意，只考虑所选择的道路集合是否相同，而不考虑山羊卡丁车在这些道路上的行驶方向。

输入格式

第一行输入包含 $N$, $M$, $X$, 和 $Y$，其中\n$1 \leq N \leq 1500$, $1 \leq M \leq N-1$, 且 $0 \leq X, Y \leq 2500$。\n\n接下来的 $M$ 行描述道路。每行格式为：$A_i$ $B_i$ $D_i$，表示草地 $A_i$ 与草地 $B_i$ 之间有一条长度为整数 $D_i$ 的道路相连（$1 \leq A_i, B_i \leq N$, $0 \leq D_i \leq 2500$）。每个草地都至少与一条道路相连，并且道路图中没有环。\n\n在至少 70% 的测试点中，还保证 $N \leq 1000$ 且 $Y \leq 1000$。

输出格式

输出一个整数，表示所有有趣赛道的赛道长度之和。由于该值可能非常大，请输出长度之和对\n$10^9+7$\n取模的结果。

5 3 1 12\n1 2 3\n2 3 4\n4 5 6

54

提示

此样例共有 6 条可能的赛道\n1 --> 2 --> 4 --> 5 --> 1 (长度 11)\n1 --> 2 --> 5 --> 4 --> 1 (长度 11)\n2 --> 3 --> 4 --> 5 --> 2 (长度 12)\n2 --> 3 --> 5 --> 4 --> 2 (长度 12)\n1 --> 2 --> 3 --> 4 --> 5 --> 1 (长度 15)\n1 --> 2 --> 3 --> 5 --> 4 --> 1 (长度 15)\n答案为 $12+12+15+15=54$，只累加长度至少为 $12$ 的赛道。\n\n注意：本题的标准时限被提高到每个测试用例 3 秒（Java 和 Python 为每个测试用例 6 秒）。\n\n题目致谢：Matt Fontaine

标签: USACO|2019|Platinum

来源

USACO|2019|Platinum