Miško sa stal vedúcim strategického oddelenia energetickej spoločnosti, ktorá vlastní viacero elektrární. Každá energetická spoločnosť je platená za to, že poskytuje elektrinu domácnostiam, ktorá sa tam dostane z elektrární pomocou elektrického vedenia. Popíšme si zjednodušený model.
Máme graf, ktorý reprezentuje celú sieť. Vrcholy v grafe sú buď:
Hrana z $A$ do $B$ reprezentuje elektrické vedenie, ktoré je schopné preniesť najviac $c$ jednotiek elektriny týmto smerom, kde $c$ je kapacita hrany. Môže ale prenášať aj menšie množstvo elektriny.
Elektrina sa v uzloch nesmie hromadiť. To znamená, že pre každý uzol musí platiť: Množstvo elektriny, ktoré do uzlu vchádza je rovnaké, ako množstvo elektriny, ktoré z neho vychádza.
Miškovou úlohou je poskytnúť čo najviac elektriny domácnostiam s dostupnou infraštruktúrou. Pre každú hranu má určiť množstvo elektriny, ktoré ňou má prechádzať. Pritom toto priradenie musí spĺňať horeuvedené požiadavky.
Pomôžte mu nájsť najlepšie možné riešenie, v ktorom je celkové množstvo elektriny dodané domácnostiam v súčte najväčšie možné.
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 1\,000$. ($m$ je zhora obmedzené podmienkami, ktoré uvedieme neskôr.)
V ďalšom riadku je $n$ čísel oddelených medzerou, $i$-te z nich popisuje $i$-ty vrchol. Pre elektráreň je to číslo $0$, pre uzol $1$ a pre domácnosť $2$.
Nasleduje $m$ riadkov, každý z nich určuje jednu hranu. Pozostáva z troch medzerou oddelených celý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$.
Môžete predpokladať $m^2 \cdot C < 2 \cdot 10^9$, kde $C$ je najväčšia kapacita hrany.
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 hrana vychádza, do ktorého vchádza, a množstvo elektriny posielanej po tejto hrane.
Množstvo prenášanej elektriny nemusí byť celočíselné. Kvôli nepresnostiam pri výpočtoch s desatinnými číslami vám ale odporúčame, aby ste našli riešenie, ktoré má tieto hodnoty celočíselné. Je zaručené, že existuje také riešenie.
5 7
1 2 2 1 0
4 3 6
4 1 2
0 3 5
0 2 3
0 1 7
3 1 7
3 2 4
5
0 1 0
3 1 6
3 2 0
4 3 6
4 1 2