==== 3. ÚLOHA ====

Výstavba potrubní pošty

[[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|}}

[[http://www.scribd.com/doc/6853671/Tarjan-Finding-optimum-branchings|Tarjanuv clanek]]

[[http://jdem.cz/cemh5|Problém hledání minimální kostry orientovaného grafu]]


[[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