Programozás‎ > ‎Feladatok‎ > ‎

Festmények értéke

Kiállításokon járva gyakran szeretnénk megtudni egy kép történetét. Az egyik gyakori kérdés az, hogy milyen más művek inspirálták a festőt a kép készítésekor. Ha egy alkotó "nagy" művészektől merített, akkor őt is "nagyobbnak" tekintik. 
Mivel nagy művész akarsz lenni, nem alapozhatod karrieredet jelentéktelen alkotásokra. Festmények egy válogatását vizsgálva szeretnéd pontosan meghatározni a képek értékét. 
Ez az érték meghatározható olyan adatok alapján, amelyeket művészettörténészek pontosan dokumentáltak. A képzőművészetek numerikus történetét kutató szakemberek szerint egy festmény értéke két összetevőből számítható ki:
  • Az egyik tényező a kép belső értéke (mérete, a felhasznált színek száma,... alapján)
  • A másik pedig az örökölt nagyság: ha az A kép P százalékban merített a B festményből, akkor ez megnöveli értékét a B értékének P-szeresével. 
Előfordulhat persze, hogy A és B egyidőben készült, és mindkettő épített a másikra, de ez olyan nehézkessé tenné a számításokat, hogy a történészek bölcsen eltekintenek az ilyen kapcsolatok említésétől.

Feladat

Írjunk programot, ami megadja a festmények értékét.

Bemenet

A bemenet első sorában a festmények száma (<=5000) és a köztük lévő kapcsolatok száma (<=20000) található. A második sor a festmények belső értékét tartalmazza. Ezután soronként egy-egy kapcsolat leírása következik, ahol A B P azt jelenti, hogy az A festmény P százalékban a B-re alapozva készült. A képek sorszámozása 1-től kezdődik. A százalékok egy 0 és 1 közötti tizedestörttel vannak megadva.

Kimenet

A kimenet egyetlen sora szóközökkel elválasztva tartalmazza a festmények értékét. Az értékek legalább három tizedesjegyre legyenek pontosak.

Példa

Bemenet  Kimenet
3 2
0.5 1.0 2.0
1 2 .5
1 3 .2
1.4 1 2


Tesztadatok

Címkék

A feladat forrása: 24-órás programozó verseny 2013 (ch24.org)
Algoritmusok: topologikus rendezés, mélységi bejárás

megoldás