Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem S. 32. (January 2008)

S. 32. One can get to every showplace in a national park on bikeways as well. Some bikeways however are damaged by the winter weather. The damages have been estimated and a reconstruction value has been assigned to every bikeway expressing how important it would be to repair that bikeway.

The most important bikeways have to be reconstructed before the summer. It is required that during the reconstruction visitors should still be able to get to every showplace on bikeways. There is no limit on how many bikeways can be reconstructed at the same time, but reconstructing all of them is possible only during the whole spring.

Write a program to determine at most how many bikeways can be repaired during spring. According to this plan, you should also determine the maximum of the sums of reconstruction values of these bikeways.

The input file contains the description of the bikeways and the result is written to the output file. The names of these files are given as the first and second command line arguments of your program (e.g. s32 in.txt out.txt).

The first line of the input contains the number of showplaces N (at most 100) and the number of bikeways M (at most 500) connecting them, separated by spaces. Showplaces are denoted by integers 1, 2, \ldots, N. Then each of the following M lines contains three positive integers separated by a space in a form A B R, representing that this bikeway connects (in both directions) showplaces A and B, and has reconstruction value R>0 (an integer between 1 and 1000). (If R=0, then currently no reconstruction is necessary on that bikeway.)

The output of your program is a single number giving the sum of reconstruction values of the bikeways if an optimal strategy is chosen.

The source code of your program (s32.pas, s32.cpp, ...) together with a short documentation (s32.txt, s32.pdf, ...) should be submitted, also containing a short description of your solution and the name of the developer environment to use.

(10 pont)

Deadline expired on February 15, 2008.


Sorry, the solution is available only in Hungarian. Google translation

A feladat megoldása

A feladat hatékony megoldásához azt kellett észrevenni, hogy célszerűbb "visszafelé" dolgozni, azaz nem egy olyan legnagyobb összértékű úthalmazt keresni, melyet elhagyva a teljes úthálózatból az még összefüggő marad, hanem épp ennek komplementerét, azaz az üres úthálózatból kiindulva egy olyan legkisebb értékűt építeni, melyen már el tudunk jutni minden nevezetességhez. Ugyanis így a feladat nem más, mint az úthálózat gráfjában egy minimális költségű feszítő fa keresése, mely probléma megoldására felhasználhatjuk pl. Prim vagy Kruskal algortimusát. Megjegyezzük, hogy a feladat "előrefelé" is megoldható hatékonyan, ehhez azonban az előbbieknél lényegesen bonyolultabb algoritmus(ok), ill. adatstruktúrák szükségesek.

A mintamegoldás Kruskal algoritmusának unió-holvan adatszerkezettel történő megvalósítását mutatja be. Ha az úthálózat éleinek számát e-vel jelöljük, műveletigénye O\left(e\cdot loge\right).

Engedy Balázs

C++ mintamegoldás letöltése


Statistics:

5 students sent a solution.
10 points:Szebeni Szilveszter, Véges Márton.
9 points:Godó Zita.
8 points:1 student.
5 points:1 student.

Problems in Information Technology of KöMaL, January 2008