Táto úloha nadväzuje na úlohu Elektrárne 2, odporúčame vám preto najprv prečítať zadanie tej úlohy.
Miškovi sa podarilo prísť s plánom, ktorý maximalizoval celkové množstvo dodanej elektriny. Všimol si ale, že v ňom niektorým domácnostiam vôbec nedodáva elektrinu. Problémom sú veľké domácnosti, ktoré spotrebúvajú veľa elektriny, ktorým plán dodáva elektrinu na úkor malých domácností. Lebo sa to "oplatí".
Definujeme spokojnosť domácnosti ako podiel množstva dodanej elektriny, a limitu domácnosti. Chceme maximalizovať spokojnosť najnespokojnejšej domácnosti. Hľadáme teda najväčšie číslo $s$ také, že vieme prísť s takým plánom, že každá domácnosť má spokojnosť aspoň $s$.
Vstup má rovnaký formát, ako v predchádzajúcej úlohe. Navyše ale spĺňa $n \leq 50$.
\medskip
Na prvom riadku vstupu sú dve celé čísla oddelené medzerou: počet vrcholov $n$ a počet hrán $m$. Platí $2 \leq n \leq 50$. ($m$ je zhora obmedzené podmienkami, ktoré uvedieme neskôr.)
Nasleduje $n$ riadkov, $i$-ty z nich popisuje vrchol $i$ a obsahuje dve medzerou oddelené celé čísla $t, l$: typ vrcholu a jeho limit. $t$ je $0$ pre elektráreň, $1$ pre uzol a $2$ pre domácnosť. Platí $1 \leq l \leq 10^9$.
Posledných $m$ riadkov popisuje hrany grafu. Každý riadok pozostáva z troch medzerou oddelených čísel: odkiaľ hrana vychádza $a$, kam hrana vchádza $b$ a kapacita hrany $c$. Platí $0 \leq a, b < n$, $a \neq b$, $1 \leq c \leq 10^5$. Môžete predpokladať, že $a$ nie je domácnosť a $b$ nie je elektráreň. Pre každé $a, b$ je na vstupe najviac jedna hrana z $a$ do $b$.
Na rozdiel od predchádzajúcej úlohy, táto úloha nemá žiadne špeciálne obmedzenia.
Výstup má mať rovnaký formát ako v predchádzajúcej úlohe. Tentokrát vám ale neodporúčame hľadať optimálne riešenie s celočíselnými tokmi, nakoľko také nemusí existovať.
Na prvý riadok vypíšte $k$: počet hrán, po ktorých chcete poslať nejaké (nezáporné) množstvo elektriny.
Následne vypíšte $k$ riadkov, každý nech obsahuje tri čísla $a, b, f$ oddelené medzerou. V tomto poradí sú to: z ktorého vrcholu vychádza, do ktorého vchádza, a množstvo elektriny posielanej po tejto hrane.
Množstvo prenášanej elektriny nemusí byť celočíselné. Odporúčame ho vypisovať s presnosťou aspoň $9$ desatinných miest.
5 7
1 8
2 4
2 16
1 4
0 10
4 3 6
4 1 2
0 3 5
0 2 3
0 1 7
3 1 7
3 2 4
7
3 2 4
4 3 4
4 1 1
Všimnite si, že toto nie je najväčší možný tok. Je to ale správne riešenie, lebo spokojnosť oboch domácností je $0.25$, a väčšia najmenšia spokojnosť sa nedá dosiahnuť.