Máte někdo nápad, jaký by mohl být postup řešení?

Ja to treba delal tak, ze mam algoritmus na hledani nejmensi kostry - Kruskal (hrany ulozene v ArrayListu). Vedle toho mam int[pocetVrcholu] pole, ktere obsahuje pocet stupnu jednotlivych vrcholu. Pak si z mnoziny A vyberu vsechny kombinace K-tic - pro example na strankach zadani (12,13,16,23,26,36) a ulozim do ArrayListu. Ty mi znaci, ktere z tech hran budou mit stupen 1 pri hledani kostry.

• Nečíslovaný seznamvysledek = maxInt
• while (mamNejakeKombinace K-tic) {
• - vyndej jednu K-tici k
• - hledej kostru, pro vrcholy z k tak, ze do vrcholu z k povede jen jedna hrana (logicky ta nejlevnejsi)
• * - do kostry nepridavej hrany mezi vrcholy A
• - uloz vysledek, pokud je nizsi
• }
• kdyz vysledek = MaxInt → print -1
• else print vysledek

10/10

By bilymare: Jak myslíš to nepřidávej do kostry hrany mezi vrcholy z A… vždyt někdy tam hrany být mohou? — Marek Bílý 2013/10/08 19:22

By vlcekvl2: Podle mě má zde autor na mysli nepřidávat hrany mezi vybranou K-ticí k vrcholů. Poté by totiž nebylo možné vytvořit souvislý graf (což kostra musí být), jelikož tyto vrcholy mohou být maximálně stupně jedna.

By roziana: chci se jen zeptat, jak vytvorit k-tici kombinaci z mnoziny A?

By milanec: jo, přesně, nepřidávat mezi tou K-ticí .. to jsem se přepsal :) Na výběr K-tice z množiny A si musíš vymyslet nějaký šikovný algoritmus, nebo, jako já, najít si něco na netu a přizpůsobit si to svým potřebám :P

By bilymare:

1. A na co máš to pole stupnů vrcholů?
2. já to napsal celé dost objektově. a mám 6 z 10 (3 neustíhám a 1 je špatně).
3. mám ještě dotaz nepřeteče cena přes velikost intu?
4. implementoval si union-find stromově nebo projíždíš to pole lineárně?

…….. Díky — Marek Bílý 2013/10/09 21:01

By milanec: Pole stupňů vrcholů mi pomáhá zjišťovat, jestli jsem u té K-tice nepřekročil jejich stupeň. Velikost intu mi nepřetekla a union find jsem měl polem :)