USACO 2019 February Contest Platinum Problem 2 Moorio Kart
Bessie and Farmer John enjoy goat kart racing. The idea is very similar to Go-Kart racing that others enjoy, except the karts are pulled by goats and the track is made from nearby farmland. The farmland consists of NN meadows and MM roads, each connecting a pair of meadows.
Bessie wants to make a course from nearby farms. A farm is a subset of two or more meadows within which every meadow can reach every other meadow along a unique sequence of roads.
The nearby farmland may contain multiple farms. Suppose there are KK farms. Bessie would like to make a goat kart loop by connecting all KK farms by adding KK roads of length XX. Each farm should be visited exactly once and at least one road must be traversed inside each farm.
To make the course interesting for racers, the total length of the track should be at least YY. Bessie wants to know the sum, over all such interesting tracks, of the total track lengths. A track is different from another if there are two meadows which are adjacent (after adding the roads between farms) in one track but not the other. Please note that only the roads chosen matter, and not the direction the goat karts will travel along those roads.
INPUT FORMAT (file mooriokart.in):
The first line of input contains NN, MM, XX, and YY where 1≤N≤15001≤N≤1500, 1≤M≤N−11≤M≤N−1, and 0≤X,Y≤25000≤X,Y≤2500.Each of the MM following lines describe roads. The lines are of the form: AiAi BiBi DiDi, meaning that meadows AiAi and BiBi are connected with a road of integer length DiDi (1≤Ai,Bi≤N1≤Ai,Bi≤N, 0≤Di≤25000≤Di≤2500). Each meadow is incident to at least one road, and there are no cycles of roads.
In at least 70% of the test cases, it is also guaranteed that N≤1000N≤1000 and Y≤1000Y≤1000.
OUTPUT FORMAT (file mooriokart.out):
Output a single integer, giving the sum of track lengths over all interesting tracks. As the sum of track lengths can be quite large, print the sum of lengths modulo 109+7109+7.
SAMPLE INPUT:
5 3 1 12 1 2 3 2 3 4 4 5 6
SAMPLE OUTPUT:
54
This example has 6 possible tracks
1 --> 2 --> 4 --> 5 --> 1 (length 11)
1 --> 2 --> 5 --> 4 --> 1 (length 11)
2 --> 3 --> 4 --> 5 --> 2 (length 12)
2 --> 3 --> 5 --> 4 --> 2 (length 12)
1 --> 2 --> 3 --> 4 --> 5 --> 1 (length 15)
1 --> 2 --> 3 --> 5 --> 4 --> 1 (length 15)
The answer is 12+12+15+15=5412+12+15+15=54, adding up only the tracks where the length is at least 1212.
Note that for this problem, the standard time limit is increased to 3 seconds per test case (6 seconds per case for Java and Python).
Problem credits: Matt Fontaine
以上就是关于【USACO 2019 February Contest Platinum Problem 2 Moorio Kart】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。
往期文章阅读推荐：
5金3银！2026 IOAI国际人工智能奥赛收官！中国队取得历史性突破！
AI奥赛2026国家队名单公布！ 新赛季翰林助力直通IOAI全球总决赛！
翰林AMC8视频课重磅上线！
国际竞赛真题资源免费领取
