|
|||
D — Vízelvezető árkokMinden alkalommal, amikor esik az eső John farmer földjén, egy kisebb tó keletkezik Bessie kedvenc lóheremezőjén. Ilyenkor a lóherét egy darabig elönti a víz, és jó sokáig tart, mire újra kihajt. John farmer ezért kiépített egy vízelvezető árkokból álló rendszert, amely egy közeli patakba vezeti el a vizet, hogy ne árassza el többé Bessie lóheremezőjét. Mivel John farmer kiváló mérnök, szabályozókat is felszerelt az árkok elejére, amelyekkel vezérelni tudja az egyes árkokba folyó víz sebességét. John farmer nemcsak azt tudja, hogy az egyes árkok percenként hány liter vizet képesek átereszteni, de az árkok pontos elhelyezkedését is ismeri. Az árkok a tavacskából indulnak, egymásba torkollnak, végül a patakban végződnek egy potenciálisan összetett hálózatot alkotva. Mindezen információk birtokában határozd meg, hogy maximálisan mekkora sebességgel lehet eljuttatni a vizet a tavacskából a patakba! A víz minden árokban csak egy irányba folyik, az azonban előfordulhat, hogy több árkon keresztül körbefolyik. A bemenet specifikációjaA bemenet számos tesztesetet tartalmaz. Minden teszteset első sorában két, szóközzel elválasztott egész szám szerepel: N és M (0 ≤ N ≤ 200, 2 ≤ M ≤ 200). N a John farmer által kiásott árkok számát, M pedig az árkok metszéspontjainak a számát adja meg. Az 1-es számú metszéspont a tó, az M sorszámú metszéspont pedig a patak. A következő N sor mindegyikében három egész szám szerepel: Si, Ei és Ci. Si és Ei jelölik azokat a metszéspontokat, amelyek között az i-edik árok húzódik (1 ≤ Si, Ei ≤ M). A víz ebben az árokban Si-től Ei felé folyik. Ci (0 ≤ Ci ≤ 10 000 000) az a legnagyobb sebesség, amellyel a víz át tud folyni ezen az árkon. A kimenet specifikációjaMinden tesztesetre egyetlen egész számot kell a kimenetre írni: azt a maximális sebességet, amellyel eltüntethető a víz a tavacskából. Példa bemenet
A példa bemenethez tartozó kimenet
|
|||
| Debreceni Egyetem, Informatikai Kar, v. 2019.03.01. |