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:
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.
BemenetA 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.
KimenetA 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
TesztadatokCímkékA feladat forrása: 24-órás programozó verseny 2013 (ch24.org)
Algoritmusok: topologikus rendezés, mélységi bejárás
megoldás |
Programozás > Feladatok >
