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.

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】的解答，如需了解學校/賽事/課程動態，可至翰林教育官網獲取更多信息。

往期文章閱讀推薦：

2026五大奧賽中國隊斬獲四個世界第一，全員金牌收官！

【組隊招募】經濟/數模競賽CNEC/IEO/SIC/HiMCM…組隊報名！