Připojení
Renomovaná firma ABCDEF potřebuje propojit kabeláží všechny svoje pobočky ve městě do jediné sítě S tak, aby existovalo kabelové spojení mezi každými dvěma pobočkami. Na délce spojení mezi libovolnou dvojicí poboček P1 a P2 nezáleží, signál na své cestě může procházet více dalšími pobočkami než z P1 dorazí do P2 nebo obráceně z P2 do P1.Dále firma potřebuje síť S připojit na velkou národní síť NS, a to hned v několika pobočkách. Takové pobočky, které budou připojeny k národní síti, se nazývají kontaktní. Anylytické oddělení firmy vytipovalo množinu A poboček, z nichž každá může být kontaktní. Ředitelství firmy vyžaduje, aby kontaktních poboček bylo alespoň K, kde K je celé kladné číslo, jehož velikost naštěstí nepřevyšuje mohutnost množiny poboček A, jinak by úloha byla neřešitelná. Další významnou omezující podmínkou pro stavbu sítě S je to, že díky technickým omezením může každé z kontaktní pobočky vést do sítě S pouze jediný kabel.
Není ale možné položit kabel mezi dvěma úplně libovolnými pobočkami. Analytické oddělení má k dispozici tabulku T, jejíž řádky a sloupce jsou indexovány jednotlivými pobočkami a v tabulce na pozici [i][j] je vepsána hodnota 0, pokud dvojici poboček i a j přímo kabelem propojit nelze, a pokud tyto pobočky propojit lze, je na pozici [i][j] vepsána kladná celočíselná cena za vybudování tohoto propojení. Každé propojení funguje vždy obousměrně.
Vstup
Na vstupu je nejprve řádek s celým číslem N označujícím počet poboček ve městě. Pobočky ve městě jsou očíslovány 1..N. Na dalších N řádcích je uvedena tabulka T, každý řádek vstupu obsahje jeden řádek tabulky, na řádku je N celých nezáporných čísel oddělených jednou nebo více mezerami. Na dalším řádku za tabulkou je uvedena množina A možných kontaktních poboček. První číslo na řádku určuje mohutnost množiny A, dále je uvedeno |A| čísel poboček zapsaných v nespecifikovaném pořadí, údaje na řádku jsou odděleny alespoň jednou mezerou. Poslední řádek vstupu představuje minimální požadovaný počet kontaktních poboček K.Vstup je zadán korektně, není třeba kontrolovat jeho správnost.
Počet poboček leží vždy v rozmezí 3 až 99.
Výstup
Na výstupu je jediný řádek s jedním celým číslem představujícím minimální cenu, za níž je možno kabeláží propojit všechny pobočky při zachování všech daných omezení. Pokud požadované propojení nelze vybudovat, vystoupí řádek s číslem -1.Poznámka
Počet takových poboček ve výsledné síti S, které budou se zbytkem S propojeny jediným kabelem, může nakonec být větší než zadané K, tím ale není nijak ovlivněna podmínka, že jen K z nich (a z množiny A) bude připojeno na národní síť NS.Příklad 1
Vstup:6 0 3 0 1 0 0 3 0 3 0 1 0 0 3 0 0 0 1 1 0 0 0 9 0 0 1 0 9 0 6 0 0 1 0 6 0 4 1 2 3 6 2Výstup:
14
Příklad 2
Vstup:7 0 0 7 0 0 0 0 0 0 0 7 0 0 7 7 0 0 7 7 0 0 0 7 7 0 0 7 0 0 0 7 0 0 0 0 0 0 0 7 0 0 7 0 7 0 0 0 7 0 2 4 3 1Výstup:
-1V příkladu 2 úloha nemá řešení. Je nutno vybrat z poboček 3, 4 alespoň jednu tak, že z ní vede jen jediný kabel dovnitř sítě S. S touto podmínkou není možné siť vybudovat tak, aby byla souvislá, např. nelze pak propojit pobočky 1 a 6. Obrázek ukazuje sítě pro příklad 1 a 2, tučnou čarou je znázorněno optimální propojení.
Obr 1. Sítě z příkladů.
18 0 0 0 67 0 20 0 0 64 50 0 88 68 0 62 32 0 0 0 0 82 43 0 53 0 0 0 17 64 0 0 0 0 0 0 37 0 82 0 0 41 38 35 0 0 0 0 0 0 0 0 0 24 0 67 43 0 0 0 0 0 0 0 0 1 0 80 0 0 0 0 0 0 0 41 0 0 75 48 0 45 0 0 0 0 23 0 0 0 50 20 53 38 0 75 0 67 0 0 0 0 12 0 0 0 48 0 0 0 0 35 0 48 67 0 71 0 0 0 26 0 0 0 0 92 0 0 0 0 0 0 0 71 0 0 0 62 0 0 0 0 0 86 93 64 0 0 0 45 0 0 0 0 0 14 63 69 0 76 63 3 71 50 17 0 0 0 0 0 0 0 0 52 0 0 0 0 51 0 0 0 64 0 1 0 0 0 62 14 52 0 0 96 73 0 0 0 34 88 0 0 0 0 12 26 0 63 0 0 0 0 0 0 66 0 0 68 0 0 80 0 0 0 0 69 0 96 0 0 0 0 0 0 43 0 0 0 0 23 0 0 0 0 0 73 0 0 0 0 0 0 0 62 0 0 0 0 0 0 0 76 0 0 0 0 0 0 66 0 0 32 0 0 0 0 48 0 0 63 51 0 66 0 0 66 0 0 0 0 0 24 0 0 0 92 86 3 0 0 0 0 0 0 0 0 0 0 37 0 0 50 0 0 93 71 0 34 0 43 0 0 0 0 0 7 16 12 8 5 17 18 6 3Výstup:
498
Příklad 4
Vstup:25 0 1 0 51 0 0 20 59 35 17 94 46 14 92 0 0 64 95 34 78 84 41 26 23 7 1 0 0 12 23 0 15 51 67 63 63 0 76 0 0 71 60 72 0 97 0 43 92 23 38 0 0 0 19 64 62 86 5 0 13 19 0 70 73 89 96 80 43 26 3 69 76 25 0 70 51 12 19 0 50 0 10 0 31 99 0 44 97 88 0 52 57 64 0 65 0 71 32 95 48 0 23 64 50 0 48 0 0 24 0 43 0 15 0 83 0 0 0 83 65 72 19 99 26 31 0 0 62 0 48 0 64 56 0 51 5 0 0 90 60 0 99 0 0 0 99 0 0 6 50 20 15 86 10 0 64 0 93 29 17 61 4 42 32 42 0 0 0 6 31 63 9 0 33 41 59 51 5 0 0 56 93 0 0 71 34 0 47 43 74 55 88 0 17 0 38 0 37 29 87 35 67 0 31 24 0 29 0 0 81 0 11 58 51 0 95 0 0 32 3 24 30 73 66 83 17 63 13 99 0 51 17 71 81 0 82 24 27 0 0 30 18 0 0 48 89 43 32 43 77 94 63 19 0 43 5 61 34 0 82 0 20 33 0 0 99 69 0 81 56 0 57 65 34 0 46 0 0 44 0 0 4 0 11 24 20 0 33 0 0 0 0 15 1 56 92 91 98 30 29 14 76 70 97 15 0 42 47 58 27 33 33 0 4 0 35 0 57 89 18 94 66 35 53 0 92 0 73 88 0 90 32 43 51 0 0 0 4 0 42 99 18 55 0 34 66 62 55 98 0 0 0 89 0 83 60 42 74 0 0 0 0 0 42 0 0 75 95 30 0 19 0 93 61 34 0 71 96 52 0 0 0 55 95 30 99 0 35 99 0 0 0 45 40 46 50 38 68 59 46 64 60 80 57 0 99 0 88 0 18 69 0 0 18 75 0 0 54 8 64 53 78 52 28 41 95 72 43 64 0 0 0 0 0 0 0 15 57 55 95 45 54 0 12 29 99 26 38 0 35 34 0 26 0 83 0 6 17 32 0 81 1 89 0 30 40 8 12 0 57 85 0 45 0 65 78 97 3 65 65 0 31 0 3 48 56 56 18 34 0 46 64 29 57 0 73 0 0 29 68 84 0 69 0 72 99 63 38 24 89 0 92 94 66 19 50 53 99 85 73 0 53 72 20 0 41 43 76 71 19 0 9 0 30 43 57 91 66 62 0 38 78 26 0 0 53 0 67 86 30 26 92 25 32 99 0 0 37 73 32 65 98 35 55 93 68 52 38 45 0 72 67 0 55 0 23 23 0 95 26 6 33 29 66 43 34 30 53 98 61 59 28 0 0 29 20 86 55 0 93 7 38 70 48 31 50 41 87 83 77 0 29 0 0 34 46 41 35 65 68 0 30 0 93 0 20 8 7 18 3 6 20 16 5 24 9 22 15 19 25 2 1 12 13 4 21 4Výstup:
256