5. Úžasná lyžovačka (vzorové riešenie) - Korešpondenčný seminár z programovania

Zadanie

Kristína a Aďo sa vybrali na lyžovačku do Tatier. Bohužiaľ, kvôli pandemickým opatreniam sú všetky vleky a lanovky vypnuté. Sú ale odhodlaní lyžovať sa aj za cenu toho, že si budú musieť kopec zakaždým vyšliapať po svojich. Aby sa ale nestratili, budú kráčať po iba po svahoch medzi stanicami lanoviek.

Po prvom výstupe ale zistili, že šliapať do kopca v lyžiarkach je nesmierne náročné, a že čím strmší kopec je, tým viac sú potom vyčerpaní. Aby si ušetrili čo najviac energie na zjazdy, rozhodli sa, že hore radšej pôjdu po čo najmenej strmých kopcoch aj za cenu toho, že ich cesta bude dlhšia.

Samozrejme, ak sa niekde počas ich cesty na vrch objaví úsek na ktorom pôjdu dole kopcom, neváhajú a spustia sa na lyžiach. Je tu ale jeden drobný problém – Aďo je začiatočník a preto nerád jazdí po strmých kopcoch. Chcel by teda, aby aj dole išli po čo najmenej strmých kopcoch.

Zapozerali sa teda do mapy strediska a začali hľadať čo najmenej strmú cestu na kopec, ktorý si vybrali. Stredisko je ale príliš veľké, a tak to po chvíľke vzdali. Keby si tak zobrali so sebou počítač, určite by niečo vymysleli. Ten ale nemajú a preto potrebujú vašu pomoc.

Úloha

Stredisko pozostáva z \(v\) staníc lanoviek, pričom poznáme nadmorské výšky každej z nich. Na jednej z nich, označenej číslom \(s\), stoja Kristína a Aďo, ktorí sa chcú dostať na kopec so stanicou s číslom \(f\).

V stredisku je \(e\) svahov, z ktorých každý spája dve stanice lanoviek, pričom poznáme vzdušnú vzdialenosť staníc ktoré spája. Uvažujeme, že svah je na celom svojom úseku rovnako strmý a jeho strmosť je určená podielom rozdielu prevýšení staníc a jeho vzdušnou vzdialenosťou.

Vašou úlohou je nájsť takú cestu z \(s\) do \(f\), aby maximálna strmosť svahov na tejto ceste bola čo najmenšia.

Formát vstupu

Na prvom riadku dostanete štyri čísla \(v, e, s, f\), kde \(v\) je počet staníc lanoviek, \(e\) je počet svahov v stredisku, \(0 \leq s < v\) je číslo stanice lanovky na ktorej Kristína a Aďo začínajú a \(0 \leq f < v\) je číslo stanice, na ktorú sa chcú dostať. (Stanice lanoviek sú číslované od \(0\).)

Nasleduje \(v\) riadkov, kde každý riadok obsahuje celé číslo \(h_i\) – nadmorskú výšku \(i\)-tej stanice lanovky.

Ďalších \(e\) riadkov obsahuje tri celé čísla \(a_j, b_j, d_j\), kde \(a_j\) a \(b_j\) sú čísla staníc prepojených \(j\)-tým svahom a \(d_j\) je vzdušná vzdialenosť staníc \(a_j\) a \(b_j\).

Formát výstupu

Vypíšte jediné číslo – strmosť najstrmšieho svahu na ceste z \(s\) do \(f\), s presnosťou na práve dve desatinné miesta.

Hodnotenie

Sú 4 sady vstupov. Platia v nich nasledujúce obmedzenia:

Sada	\(1\)	\(2\)	\(3\)	\(4\)
\(1 \leq v \leq\)	\(20\)	\(100\)	\(2\,500\)	\(9\,000\)
\(1 \leq e \leq\)	\(50\)	\(500\)	\(5\,000\)	\(20\,000\)

Príklad

Input:

Output:

0.68

Vhodné cesty sú \([0, 1, 2, 3]\) a \([0, 2, 3]\). Obe cesty sú ale rovnako dobré, keďže majú rovnakú najstrmšiu časť – svah medzi stanicami \(2\) a \(3\).

Už na prvý pohľad je asi vcelku zrejmé, že lyžiarske stredisko si vieme predstaviť ako neorientovaný ohodnotený graf, v ktorom stanice lanoviek budú vrcholmi a svahy hranami grafu. Ceny hrán budú strmosti svahov, ktoré si vypočítame už pri načítavaní vstupu.

Priamočiare riešenie

Môžeme si všimnúť, že na nájdenú cestu nemáme žiadne ďalšie nároky, okrem toho že existuje. Najjednoduchšie riešenie teda spočíva v tom, že z grafu odstránime všetky hrany a budeme ich postupne pridávať v poradí od najmenej strmej. Po každom pridaní hrany skontrolujeme, či neexistuje cesta medzi \(s\) a \(f\). V momente, ako takúto cestu nájdeme, môžeme skončiť, keďže všetky ďalšie hrany, ktoré by sme pridali by mali vyššiu strmosť. Naopak, lepšie riešenie tiež nemôže existovať, keďže by sme ho už našli skôr. Zároveň už poznáme aj najstrmšiu hranu v nájdenej ceste – je ňou posledná pridaná hrana.

V našej implementácii nám bude teda stačiť, keď si po načítaní uriedime hrany podľa strmosti, v cykle ich budeme pridávať do grafu (ideálne reprezentovaného ako zoznam susedov) a existenciu cesty overíme napríklad pomocou BFS (prehľadávania do šírky). Časová zložitosť takéhoto riešenia je \(O(e \cdot (v + e))\). V najhoršom prípade totiž postupne pridáme do grafu všetky hrany, čo znamená, že BFS budeme musieť spustiť až \(e\)-krát. Pamäťová zložitosť je \(O(v + e)\).

Za implementáciu s maticou susedov ste mohli dostať až 4 body, za šikovnú implementáciu so zoznamom susedov dokonca až 6 bodov.

from collections import deque

v, e, start, end = (int(x) for x in input().split())
heights = [int(input()) for _ in range(v)]

edges = []
for _ in range(e):
    a, b, d = (int(x) for x in input().split())
    slope = abs(heights[a] - heights[b]) / d
    edges.append((slope, a, b))
edges.sort()

neighbors = {x: {} for x in range(v)}
for slope, a, b in edges:
    neighbors[a][b] = neighbors[b][a] = (slope, d)

    # BFS
    explored = [False] * v
    d = deque([start])
    explored[start] = True

    while len(d):
        next = d.popleft()
        if next == end:
            break

        for neighbor, edge in neighbors[next].items():
            if not explored[neighbor]:
                explored[neighbor] = True
                d.append(neighbor)

    if next == end:
        print(f'{slope:0.2f}')
        break

#include <iostream>
#include <vector>
#include <unordered_map>
#include <set>
#include <deque>
#include <iomanip>
#include <algorithm>
using namespace std;

typedef tuple<double, int, int> Edge;

int main() {
    int v, e, s, f;
    cin >> v >> e >> s >> f;

    vector<int> heights(v);
    for (int i = 0; i < v; i++) {
        cin >> heights[i];
    }

    vector<Edge> edges(e);
    for (int i = 0; i < e; i++) {
        int a, b, d;
        cin >> a >> b >> d;
        double slope = abs((heights[a] - heights[b])) / double(d);
        edges[i] = make_tuple(slope, a, b);
    }
    sort(edges.begin(), edges.end());

    unordered_map<int, set<int>> neighbors;
    for (const auto &edge : edges) {
        neighbors[get<1>(edge)].insert(get<2>(edge));
        neighbors[get<2>(edge)].insert(get<1>(edge));

        // BFS
        vector<bool> explored(v, false);
        deque<int> d;
        d.push_back(s);
        explored[s] = true;

        while (!d.empty()) {
            int next = d.front();
            d.pop_front();

            if (next == f) {
                cout << fixed << showpoint << setprecision(2) << get<0>(edge) << endl;
                return 0;
            }

            for (const auto &neighbor : neighbors[next]) {
                if (!explored[neighbor]) {
                    explored[neighbor] = true;
                    d.push_back(neighbor);
                }
            }
        }
    }

    return 0;
}

Ako to zrýchlime?

Z predchádzajúceho riešenia už asi tušíme, že hlavný problém je v počte spustení BFS. Naozaj musíme pridávať hrany po jednej a zakaždým skúšať, či existuje riešenie? Samozrejme, že nie!

To, čo sme robili v predchádzajúcom riešení si môžme predstaviť aj trochu inak: V podstate sme hľadali posledný prvok najmenšieho prefixu utriedeného poľa hrán \([e_0, e_1, \ldots, e_{max}]\) takého, že s pomocou týchto hrán je možné vytvoriť cestu z \(s\) do \(f\). No, a keďže je pole už utriedené, namiesto skúšania všetkých hrán si tú správnu hranu môžeme nájsť binárnym vyhľadávaním.

Samotné binárne vyhľadávanie bude prebiehať takmer rovnako ako na obyčajnom poli: Prehľadávanú oblasť rozdelíme v polovici a vyberieme prostrednú hranu \(e_{mid}\). Vyskúšame, či podgraf s hranami \(e_0\) až \(e_{mid}\) obsahuje cestu z \(s\) do \(f\). Ak áno, budeme znovu binárne prehľadávať ľavú polovicu (keďže chceme nájsť najmenej strmú hranu, ktorú potrebujeme).

Vďaka binárnemu vyhľadávaniu potrebujeme spustiť BFS už len \(\log{e}\)-krát, čiže výsledná časová zložitosť bude \(O((v + e) \cdot \log{e})\). Pamäťová zložitosť sa oproti predchádzajúcemu riešeniu nezmenila.

from collections import deque

v, e, s, f = (int(x) for x in input().split())
heights = [int(input()) for _ in range(v)]

edges = []
for _ in range(e):
    a, b, d = (int(x) for x in input().split())
    slope = abs(heights[a] - heights[b]) / d
    edges.append((slope, a, b))
edges.sort()

def bfs(edges, v, s, f):
    neighbors = {x: {} for x in range(v)}
    for slope, a, b in edges:
        neighbors[a][b] = neighbors[b][a] = slope

    # BFS
    explored = [False] * v
    d = deque([s])
    explored[s] = True

    while len(d):
        next = d.popleft()
        if next == f:
            return True

        for neighbor, _ in neighbors[next].items():
            if not explored[neighbor]:
                explored[neighbor] = True
                d.append(neighbor)

    return False


l, h = 0, e
best = -1
while h - l > 1:
    m = l + (h-l) // 2

    if bfs(edges[:m+1], v, s, f):
        h = m
        best = edges[m][0]
    else:
        l = m

print(f'{best:0.2f}')

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <deque>
#include <map>
#include <set>
using namespace std;

struct Edge {
    int a, b, d;
    int o;
    double slope;
};

struct Graph {
    int v, e, s, f;
    vector<int> heights;
    vector<Edge> edges;
};

bool cmp(const Edge &a, const Edge &b) {
    return a.slope < b.slope;
}

bool bfs(Graph &g, int maxEdge) {
    map<int, set<int>> matrix;
    for (int i = 0; i < maxEdge; i++) {
        auto &e = g.edges[i];
        matrix[e.a].insert(e.b);
        matrix[e.b].insert(e.a);
    }

    vector<bool> visited(g.v, false);
    deque<int> d;

    visited[g.s] = true;
    d.push_back(g.s);

    while (!d.empty()) {
        auto next = d.front();
        d.pop_front();

        if (next == g.f) {
            return true;
        }

        for (auto &&neighbor : matrix[next]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                d.push_back(neighbor);
            }
        }

    }

    return false;
}

int main() {
    Graph g;
    cin >> g.v >> g.e >> g.s >> g.f;

    g.heights.resize(g.v);
    for (int i = 0; i < g.v; i++) {
        cin >> g.heights[i];
    }

    for (int i = 0; i < g.e; i++) {
        Edge e;
        cin >> e.a >> e.b >> e.d;
        e.slope = abs(g.heights[e.a] - g.heights[e.b]) / double(e.d);
        g.edges.push_back(e);

    }

    sort(g.edges.begin(), g.edges.end(), cmp);

    int l = 0, h = g.e;
    double bestslope = -1;
    while (h - l > 1) {
        int m = l + (h-l) / 2;

        if (bfs(g, m+1)) {
            h = m;
            bestslope = g.edges[m].slope;
        } else {
            l = m;
        }
    }

    cout << fixed << showpoint << setprecision(2) << bestslope << endl;

    return 0;
}

Riešenie s kostrami

Táto úloha sa dala riešiť aj trochu inak: Ak si na začiatku nájdeme minimálnu kostru grafu reprezentujúceho lyžiarske stredisko, dostaneme vlastne graf, v ktorom už nie sú žiadne nadbytočné drahšie hrany. Medzi každou dvojicou vrcholov teda bude existovať už len jedna cesta, ktorej maximálna strmosť bude najmenšia možná. Na to, aby sme túto cestu našli nám opäť bude stačiť BFS alebo podobný algoritmus.

Navyše, ak si mierne upravíme Kruskalov algoritmus, nebudeme dokonca potrebovať ani BFS. Rovnako ako v Kruskalovom algoritme budeme postupne pridávať najlacnejšie hrany, pričom každá nová hrana nám spojí dva komponenty grafu. Ak sa nám teda niekedy vyskytnú vrcholy \(s\) a \(f\) v rovnakom komponente, vieme, že existuje medzi nimi cesta. Stačí nám teda po každej pridanej hrane skontrolovať v akých komponentoch sú \(s\) a \(f\). A keďže nehľadáme minimálnu kostru, cykly v grafe nám nevadia a nemusíme dokonca ani vynechávať hrany.

Takéto riešenie má časovú zložitosť iba \(O(e \log e)\). Toto riešenie by sa dalo ešte zrýchliť efektívnejšou implementáciou Union-Find až na \(O(e \log^* e)\)¹. Pamäťová zložitosť zostáva stále rovnaká, čiže \(O(v + e)\).

v, e, start, end = (int(x) for x in input().split())
heights = [int(input()) for _ in range(v)]
parents = list(range(v))

edges = []
for _ in range(e):
    a, b, d = (int(x) for x in input().split())
    slope = abs(heights[a] - heights[b]) / d
    edges.append((slope, a, b))
edges.sort()

def find(i):
    if parents[i] == i:
        return i
    else:
        parents[i] = find(parents[i])
        return parents[i]

def union(a, b):
    a, b = find(a), find(b)
    if a == b:
        return
    parents[a] = b

for slope, a, b in edges:
    union(a, b)
    if find(start) == find(end):
        print(f'{slope:0.2f}')
        break

#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;

typedef tuple<double, int, int> Edge;
vector<int> parents;

int find(int i) {
    return parents[i] == i ? i : parents[i] = find(parents[i]);
}

void uni(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return;
    parents[a] = b;
}

int main() {
    int v, e, s, f;
    cin >> v >> e >> s >> f;

    vector<int> heights(v);
    parents.resize(v);
    for (int i = 0; i < v; i++) {
        cin >> heights[i];
        parents[i] = i;
    }

    vector<Edge> edges(e);
    for (int i = 0; i < e; i++) {
        int a, b, d;
        cin >> a >> b >> d;
        double slope = abs((heights[a] - heights[b])) / double(d);
        edges[i] = make_tuple(slope, a, b);
    }
    sort(edges.begin(), edges.end());

    for (const auto &edge : edges) {
        uni(get<1>(edge), get<2>(edge));
        if (find(s) == find(f)) {
            cout << fixed << showpoint << setprecision(2) << get<0>(edge) << endl;
            break;
        }
    }

    return 0;
}

\(\log^*\) je iterovaný logaritmus↩︎

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.

5. Úžasná lyžovačka vzorové riešenie