KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up


Problem S. 103. (December 2015)

S. 103. There are \(\displaystyle N\) towns in a country. Your task is to design a road network such that one can travel between any two towns in exactly one way. The cost of building a particular road segment is directly proportional to its length, so we would like to minimize the total length of the network. However, there are also some hills in the country, making it impossible to build a road between any two arbitrary towns: it is only allowed to construct certain \(\displaystyle M\) roads specified by the input data. Moreover, due to some technical restrictions, the construction company cannot build more than three roads of a given length, hence the network should be designed such that there are at most three roads of any given length. Your program should determine the number of ways the network with the minimum total length can be built.

Your program should read the values of \(\displaystyle N\) and \(\displaystyle M\) (\(\displaystyle 1\le N \le 50\;000\), \(\displaystyle 1\le M\le 200\;000\)) from the first line of the standard input; then the \(\displaystyle a_i\), \(\displaystyle b_i\) and \(\displaystyle c_i\) integers (separated by a space) from the following \(\displaystyle M\) lines, representing the fact that a two-way road can be built from town \(\displaystyle a_i\) to town \(\displaystyle b_i\) with cost \(\displaystyle c_i\) (\(\displaystyle 1\le c_i\le 1\;000\;000\)). The first and only line of the standard output should contain the minimum total length of a valid network, moreover, the remainder on division of the number of possible networks by \(\displaystyle 1\;000\;000\;007\).

Explanation: The minimum total length is achieved if we choose the edges of length 1 and one edge of length 2.

Scoring and bounds. You can get 1 point for a brief and proper documentation clearly describing your solution. Nine further points can be obtained provided that your program solves any valid input within 1 second of running time.

The source code of your program and a short documentation-also describing which developer environment to use for compiling the source-should be submitted in a compressed file s103.zip.

(10 pont)

Deadline expired on 11 January 2016.


14 students sent a solution.
10 points:Csenger Géza, Erdős Márton, Gáspár Attila, Noszály Áron.
5 points:1 student.
3 points:3 students.
2 points:3 students.
0 point:3 students.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley