navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m33pal:uloha3 [2009/10/27 23:09] dundee |
courses:a4m33pal:uloha3 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 3: | Řádek 3: | ||
| Výstavba potrubní pošty | Výstavba potrubní pošty | ||
| - | [[http://cmp.felk.cvut.cz/cmp/courses/a4m33pal/task.php?task=potrubni_posta|Zadání]] | + | [[courses/a4m33pal/uloha3/popis-alg| Popis algoritmu]] |
| + | |||
| + | [[courses/a4m33pal/uloha3/zadani | Zadání]] | ||
| + | |||
| + | Limit: 40s | ||
| + | |||
| + | [[courses/a4m33pal/uloha3/utility| Utility, které se mohou hodit]] | ||
| + | |||
| + | [[courses/a4m33pal/uloha3/generator| Generátor vstupu]] | ||
| {{:courses:a4m33pal:algorithm-description.pdf|}} | {{:courses:a4m33pal:algorithm-description.pdf|}} | ||
| [[http://www.scribd.com/doc/6853671/Tarjan-Finding-optimum-branchings|Tarjanuv clanek]] | [[http://www.scribd.com/doc/6853671/Tarjan-Finding-optimum-branchings|Tarjanuv clanek]] | ||
| - | |||
| - | [[http://algowiki.net/wiki/index.php/Edmonds%27s_algorithm|Edmondsuv algoritmus (ne Tarjanova implementace) v Jave]] | ||
| [[http://jdem.cz/cemh5|Problém hledání minimální kostry orientovaného grafu]] | [[http://jdem.cz/cemh5|Problém hledání minimální kostry orientovaného grafu]] | ||
| - | ~~DISCUSSION~~ | + | |
| + | [[http://www.algoritmy.net/article/1673/Edmondsuv-algoritmus|Chu-Liu-Edmondsův algoritmus na Algoritmy.net]] | ||
| + | |||
| + | ==== Testovací data ==== | ||
| + | Protože si člověk nemůže být jist, zda pro budoucí dají také k dispozici testovací data, tak přidávám testovací data, která nám po přidali + výstup z mého programu. Kdyby mi někdo ve výstupech našel chybu, nechť ji prosím opraví. | ||
| + | |||
| + | |||
| + | {{:courses:a4m33pal:courses:a4m33pal:uloha3:priklady.zip|Oficiální testovací data navíc}} | ||
| + | |||
| + | ---- | ||
| + | Test spravneho prepocitavani cen v Tarjanovi(Edmondsuv algoritmus) | ||
| + | == In: == | ||
| + | |||
| + | 6 | ||
| + | |||
| + | 0 1 1 | ||
| + | |||
| + | 0 2 1 | ||
| + | |||
| + | 0 3 1 | ||
| + | |||
| + | 0 4 1 | ||
| + | |||
| + | 0 5 1 | ||
| + | |||
| + | 1 2 1 | ||
| + | |||
| + | 2 3 2 | ||
| + | |||
| + | 3 4 3 | ||
| + | |||
| + | 4 5 4 | ||
| + | |||
| + | 5 1 5 | ||
| + | |||
| + | 0 0 0 | ||
| + | |||
| + | == Out: == | ||
| + | |||
| + | 5 | ||
| + | |||
| + | 0 | ||
| + | |||
| + | 0 5 1 | ||
| + | |||
| + | 0 4 1 | ||
| + | |||
| + | 0 3 1 | ||
| + | |||
| + | 0 2 1 | ||
| + | |||
| + | 0 1 1 | ||
| + | |||
| + | 0 0 0 | ||
| + | |||
| + | ---- | ||
| + | Testovani spravneho rozbalovani cyklu (resp. spravneho prorezavani) | ||
| + | == In: == | ||
| + | |||
| + | 10 | ||
| + | |||
| + | 0 1 20 | ||
| + | |||
| + | 1 2 1 | ||
| + | |||
| + | 2 3 1 | ||
| + | |||
| + | 3 4 1 | ||
| + | |||
| + | 4 5 1 | ||
| + | |||
| + | 5 0 1 | ||
| + | |||
| + | 0 6 1 | ||
| + | |||
| + | 6 7 1 | ||
| + | |||
| + | 7 8 1 | ||
| + | |||
| + | 8 5 100 | ||
| + | |||
| + | 9 0 200 | ||
| + | |||
| + | 0 0 0 | ||
| + | |||
| + | == Out: == | ||
| + | |||
| + | 227 | ||
| + | |||
| + | 9 | ||
| + | |||
| + | 9 0 200 | ||
| + | |||
| + | 7 8 1 | ||
| + | |||
| + | 6 7 1 | ||
| + | |||
| + | 0 6 1 | ||
| + | |||
| + | 4 5 1 | ||
| + | |||
| + | 3 4 1 | ||
| + | |||
| + | 2 3 1 | ||
| + | |||
| + | 1 2 1 | ||
| + | |||
| + | 0 1 20 | ||
| + | |||
| + | 0 0 0 | ||
| + | ---- | ||
| + | Testovani nalezeni spravneho korene. | ||
| + | == In: == | ||
| + | 9 | ||
| + | |||
| + | 4 5 20 | ||
| + | |||
| + | 5 6 1 | ||
| + | |||
| + | 6 7 1 | ||
| + | |||
| + | 7 8 1 | ||
| + | |||
| + | 8 3 1 | ||
| + | |||
| + | 0 1 1 | ||
| + | |||
| + | 1 2 1 | ||
| + | |||
| + | 2 3 1 | ||
| + | |||
| + | 3 4 100 | ||
| + | |||
| + | 4 0 1 | ||
| + | |||
| + | 0 0 0 | ||
| + | |||
| + | == Out: == | ||
| + | 27 | ||
| + | |||
| + | 4 | ||
| + | |||
| + | 8 3 1 | ||
| + | |||
| + | 7 8 1 | ||
| + | |||
| + | 6 7 1 | ||
| + | |||
| + | 5 6 1 | ||
| + | |||
| + | 4 5 20 | ||
| + | |||
| + | 1 2 1 | ||
| + | |||
| + | 0 1 1 | ||
| + | |||
| + | 4 0 1 | ||
| + | |||
| + | 0 0 0 | ||
| + | |||
| + | ---- | ||
| + | |||
| + | Prikladek z Cameriniho | ||
| + | |||
| + | == In: == | ||
| + | 4 | ||
| + | |||
| + | 0 1 6 | ||
| + | |||
| + | 1 2 10 | ||
| + | |||
| + | 2 1 10 | ||
| + | |||
| + | 1 3 12 | ||
| + | |||
| + | 3 2 8 | ||
| + | |||
| + | 3 0 1 | ||
| + | |||
| + | 0 0 0 | ||
| + | |||
| + | == Out: == | ||
| + | 15 | ||
| + | |||
| + | 3 | ||
| + | |||
| + | 0 1 6 | ||
| + | |||
| + | 3 0 1 | ||
| + | |||
| + | 3 2 8 | ||
| + | |||
| + | 0 0 0 | ||
