CSES - Spoilerit

Raitiovaunut

Etsi suurin yhtenäinen komponentti. Tähän voi käyttää esimerkiksi leveyshakua

Tietullit

Vaihtoehto A: Tehtävän voi ratkaista suoraviiivaisesti käyttämällä Dijkstran algoritmia

Vaihtoehto B: Käytetään eräänlaista syvyys- ja leveyshaun yhdistelmää. Ideana on käydä läpi ensin kaikki kaupungit mihin pääsee maksamattaa yhtään tietullia, sitten kaikki kaupungit mihin pääsee yhdellä tietullilla ja niin edelleen. Jos käsiteltävällä solmulla on naapureita joihin pääsee ilman tietullia syvyyshaetaan tietullittomia teitä pitkin niin kauan kuin niitä riittää, ja sen jälkeen käsitellään tietullin omaavia teitä leveyshaun tavoin.

Tämä kannattaa toteuttaa dequella (kaksipuolinen pino), jossa 0-painoisen kaaren päässä olevat naapurit laitetaan dequen alkuun ("syvyyshakuosa"), ja 1-painoisen kaaren päässä olevat dequen loppuun ("leveyshakuosa").

Veturit

Etsitään verkolle virittävä puu jossa kaikki kaaret kestävät mahdollisimman suuren junan, eli puun "kevyin" kaari on mahdollisimman painava.

Vaihtoehto A: muuten kaaripainot negatiivisiksi: nyt tehtävänä on etsiä pienin virittävä puu, ja sen painavin (vähiten negatiivinen) kaari.

Vaihtoehto B: muokataan Kruskallin algoritmia valitsemaan ensin painavimmat kaaret.

Alennus

Vaihtoehto A:

Hyödynnetään sitä että Dijkstran algoritmi laskee etäisyyden lähtösolmusta kaikkiin muihin solmuihin. Ajetaan Dijkstra kahdesti: ensin Syrjälästä (alku), ja sitten Metsälästä (loppu) verkon transpoosissa, eli toisessa verkossa jossa kaikki kaaret on käännetty ympäri. Näin saamme laskettua lyhimmän etäisydeen jokaisestä kaupungista sekä Syrjälään että Metsälään. Lopuksi käydään kaikki kaaret läpi, kokeillaan kuinka kallis olisi reitti jossa alennus käytettäisiiin siinä kaaressa, ja otetaan paras. Koska olemme laskeneet etäisyydet ennalta saamme reitin hinnan laskettua helposti. Esimerkiksi kaarelle a -> b hinta on etäisyysSyrjälästä[a] + kaariPaino/2 + etäisyysMetsälästä[b ].

Vaihtoehto B:

Muutetaan verkkoa sellaiseksi että voimme käyttää tavallista Dijkstraa. Uudessa verkossa alkuperäiset solmut ovat kaupunkeja joissa ollaan käyty ennen alennuskupongin käyttöä. Lisäksi tehdään verkosta kopio, jonka solmut edustavat kaupunkeja joissa ollaa käyty alennuskupongin käytön jälkeen. Lopuksi lisätään kaaria alkuperäisestä kopiosta uuteen kopioon jotka edustavat alennettuja lentoja, näiden kaarien painoksi tulee puolet alkuperäisen kaaren painosta.

Jalkapallo

Muodostetaan verkko jossa riidat ovat kaaria. Jos yhtenäinen komponentti on kaksijakoinen, sen pelaajat voidaan jakaa joukkoeisiin vain kahdella tavalla, sillä ensimmäinen henkilö voidaan laittaa kahteen joukkueeseen, ja muille ei ole vaihtoehtoja. Jos se ei ole kaksijakoinen, joukkueita ei voida jakaa mitenkään. Mahdollisten joukkueiden määrä on siis 2^(c-1) missä c on komponenttien määrä. Huomaa että kaksi jakoa joissa joukkueet ovat samanlaiset joukot mutta vain paitojen väri on vaihtunut lasketaan samoiksi (tämän vuoksi c-1 eikä c). Komponenttien määristä voi pitää kirjaa laskurilla.

Haasteena on enää pitää kirjaa siitä kumpaan joukkueeseen pelaajat on valittu. Uudessa riidassa on kaksi tapausta:

a) Riita on komponentin sisällä. Nyt tarvitsee vain tarkistaa rikkooko tämä riita kaksijakoisuuden. Jos rikkoo, on vastaus 0, jos ei, mitään ei tarvitse tehdä.

b) Riita yhdistää kaksi komponenttia. Jos riidan osapuolet on sijoitettu alunperin eri joukkueisiin, ei tarvitse tehdää mitään, jaot ovat yhä validit. Jos taas riidan osapuolet ovat samassa joukkueessa, toisen joukkueen jaot pitää kääntää toisin päin. Tämän voi tehdä bruteforcella kunhan aina kääntää pienemmän komponentin jaot.

Toinen vaihtoehto jakojen vaihtoon on muokata union-find rakennetta. Talletetaan jokaiseen solmun tieto siitä onko sen solmun alipuun jaot käännetty. Nyt jos meidän täytyy kääntää jonkun komponentin jaot, vaihdamme vain sen union-findin juuren arvoa. Jos se oli 0, eli ei käännetty, siitä tulee 1, ja päinvastoin. Nyt värin selvittäminen vaikeutuu hieman. Kuljetaan solmusta komponentin juuren, ja jokaiselle ykkösellä vaihdetaan jakoa. Esimerkiksi, jos matkalla juureen on kolme ykköstä joukkue on 0 -> 1 -> 0 -> 1, eli 1. Tämän voi kätevästi laskea xorilla (x ^= arvo).

Tiet

Tehtävänä on valita puu joka yhdistää kolme tärkeää taloa, ja on mahdollisimman pieni. Tämä puu on aina saman kaltainen, siinä on joku tietty piste jonka kautta kaikki reitit kulkevat, eli kaikilla kolmella reitillä talosta toiseen kuljetaan tämän pisteen kautta. Lisäksi polut tähän "keskipisteeseen" ovat aina lyhimpiä polkuja talosta siihen pisteeseen. Huomaa että erikoistapauksena tämä piste voi olla yksi taloista.

Ideana on käydä kaikki pisteet läpi, ja katsoa olisiko se tämä erityinen piste. Tätä varten haluamme lyhimmät etäisyydet kaikista pisteistä kaikkiin kolmeen taloon. Tämä onnistuu helposti tekemällä Dijkstra jokaisesta talosta. Nyt on helppo laskea puun paino (summa etäisyyksistä) jokaiselle pisteelle, ja valita kevyin.

Ensi viikolla on puihin liittyviä tehtäviä, niitä varten lue kkkk:sta luvut 14 ja 18 puista.