Vlak potřebuje, aby v něm byl vždy alespoň určitý počet průvodčích. Tento počet se v průběhu dne mění. Požadované počty pro každý časový úsek dne jsou v tabulce. Každý průvodčí po nástupu do práce zůstává ve vlaku 8 hodin, pak odchází a v průběhu stejného dne už nenastoupí. Vytvořte a spočtěte celočíselný program, který určí, kolik průvodčích a kdy má nastoupit do práce, když chceme minimalizovat počet potřebných průvodčích při zachování minimálních potřebného počtu v každém časovém úseku.
Myslete také na to, že průvodčí, který nastoupil o 20:00, zůstává ve vlaku až do druhého dne (04:00). lak potřebuje, aby v něm byl vždy alespoň určitý počet průvodčích. Tento počet se v průběhu dne mění. Požadované počty pro každý časový úsek dne jsou v tabulce. Každý průvodčí po nástupu do práce zůstává ve vlaku 8 hodin, pak odchází a v průběhu stejného dne už nenastoupí. Vytvořte a spočtěte celočíselný program, který určí, kolik průvodčích a kdy má nastoupit do práce, když chceme minimalizovat počet potřebných průvodčích při zachování minimálních potřebného počtu v každém časovém úseku. Myslete také na to, že průvodčí, který nastoupil o 20:00, zůstává ve vlaku až do druhého dne (04:00).
Zde je tabulka požadavků na počet průvodčích v příslušném časovém úseku dne (v hodinách):
00 -- 02: 2 02 -- 04: 2 04 -- 06: 3 06 -- 08: 5 08 -- 10: 6 10 -- 12: 5 12 -- 14: 5 14 -- 16: 8 16 -- 18: 4 18 -- 20: 3 20 -- 22: 3 22 -- 00: 2
V Říši pohádek byla postavena jednosměrná silniční síť a místního despotu by zajímalo, jaká je maximální celočíselná cirkulace v této síti (cirkulace je tok, který nemá zdroj ani stok, čili Kirchhoffovy zákony platí v každém vrcholu).
Problém je, že kromě normálních "pozemských" jednosměrných silnic bylo postaveno také 8 kouzelných hyperhran, které žádné logické zákony nerespektují. Jediný způsob, jak tyto silnice chápat, je zapsat si vektor násobnosti každé hyperhrany u každého vrcholu -- a toto číslo bude celočíselná hodnota v intervalu [-5,5]. Hyperhrana nemá jeden zdrojový a jeden cílový vrchol -- u každého vrcholu má násobnost prakticky libovolnou. Hyperhrana má kapacitu 1 -- lze ji buď použít, nebo nepoužít. Ostatní hrany mají celočíselnou kapacitu 10 000.
Říše pohádek by ráda používala své kouzelné hrany, takže si cení více, pokud najdete řešení s nimi. Celkovou cirkulaci měřte jako "součet toku každou hranou" + "100000 * počet hyperhran, které jste použili".
Vašim úkolem je navrhnout program, který zadanou úlohu vyřeší pomocí celočíselného/lineárního programování, a to včetně magických hyperhran. Na prvním řádku vstupu dostanete počet vrcholů (nejvýše 300), hran (nejvýše 60 000) a magických hyperhran (nejvýše 8). Zbytek zadání je matice incidence grafu s tím, že posledních 8 sloupců odpovídá hyperhranám.
Tato úloha je bodovaná i časově: pokud vymyslite program, který pomocí celočíselného/lineárního řešiče spočítá řešení zhruba do 90 minut, dostanete 5 bodů, pokud vymyslíte program, který spočítá řešení do zhruba 10 minut, dostanete plný počet bodů.
Váš konvertor a program by měl být schopen vyřešit tuto úlohu pro libovolný graf, ne jen pro ten zadaný (tedy řešení "optimum jsem doma napočítal za několik hodin, odevzdaný program ho jen ověří" není správné). Časové limity berte jen nahrubo, ve skutečnosti měříme a hodnotíme myšlenku vašeho řešení. Vaše programy budeme spouštět na čtyřjádrovém (osmivláknovém) Intel Core i7-3770 CPU s 16GB RAM.
Zadání: ./du2ukol2.zip