od NeverNotBluu » 21. 1. 2019 23:54
Řešení:
2) Vyrobí se bipartitní graf, kde v levé partitě jsou všichni poslanci a v pravé pro každý klub vrchol předsedy a vrchol tajemníka. Hrany se natahají z těchto dvou vrcholů klubu do každého člena toho klubu. Graf se pak klasicky doplní na síť s jednotkovými kapacitami, najde se maximální tok a pozice se pak obsadí podle těch hran, kterými tok teče.
3) Základní myšlenka je taková, že když z kružnice odeberu nejvrchnější a nejspodnější bod, stanou se mi z ní dva oblouky, což už je skoro identická úloha. Stačí tedy zametat shora dolů a když najdeme vršek kružnice, vložíme si do průřezu odkazy na Klevá a Kpravá. Na spodku kružnice je pak samozřejmě zase zahodíme.
Tohle už funguje v podstatě identicky s průniky přímek, s tím rozdílem že dva oblouky mohou mít dva společné průsečíky. To ošetřím tak, že a) když najdu průsečíky dvou oblouků, naplánuji si do kalendáře jenom ten nejvrchnější, a b) když narazím na průsečík, musím další průsečíky hledat i v té dvojici, kterou jsem právě prohodil.
[b]Řešení:[/b]
2) Vyrobí se bipartitní graf, kde v levé partitě jsou všichni poslanci a v pravé pro každý klub vrchol předsedy a vrchol tajemníka. Hrany se natahají z těchto dvou vrcholů klubu do každého člena toho klubu. Graf se pak klasicky doplní na síť s jednotkovými kapacitami, najde se maximální tok a pozice se pak obsadí podle těch hran, kterými tok teče.
3) Základní myšlenka je taková, že když z kružnice odeberu nejvrchnější a nejspodnější bod, stanou se mi z ní dva oblouky, což už je [i]skoro[/i] identická úloha. Stačí tedy zametat shora dolů a když najdeme vršek kružnice, vložíme si do průřezu odkazy na K[sub]levá[/sub] a K[sub]pravá[/sub]. Na spodku kružnice je pak samozřejmě zase zahodíme.
Tohle už funguje v podstatě identicky s průniky přímek, s tím rozdílem že dva oblouky mohou mít dva společné průsečíky. To ošetřím tak, že a) když najdu průsečíky dvou oblouků, naplánuji si do kalendáře jenom ten nejvrchnější, a b) když narazím na průsečík, musím další průsečíky hledat i v té dvojici, kterou jsem právě prohodil.