7. Krášlenie cestičiek (vzorové riešenie) - Korešpondenčný seminár z programovania

Zadanie

V Adamovej záhradke sa má konať veľká záhradnícka slávnosť, na ktorú prídu záhradníci zo široka-ďaleka. Chce, aby na túto slávnosť jeho záhradka vyzerala čo najlepšie. Už sa postaral o všetky svoje záhony, ale nepáčia sa mu cestičky, ktoré medzi nimi vedú.

Rozhodol sa, že teda záhradníkom dovolí, chodiť iba po niektorých cestičkách. Vyberie také, aby boli čo najmenej škaredé; ostatné kľudne škaredé byť môžu, lebo ich nikto neuvidí. Po vybraných cestičkách sa musí dať dostať od ľubovoľného záhonu k ľubovoľnému inému. Okrem toho mu ešte zostali nejaké peniaze, ktoré môže využiť na skrášlenie cestičiek. Skrášliť každú cestičku stojí rôzne veľa peňazí.

Pomôžte Adamovi vybrať, ktoré cestičky má nechať prístupné a určiť, ktoré ako skrášliť.

Úloha

Adamovu záhradku tvorí \(n\) záhonov, pospájaných \(m\) obojsmernými cestičkami.

Každá cestička má nejakú škaredosť \(w_i\) a cenu, za ktorú môže znížiť jej škaredosť o \(1\), \(c_i\). Adam má k dispozícii \(S\) peňazí, ktoré môže minúť na skrášľovanie cestičiek.

Vašou úlohou je vybrať \(n-1\) takých cestičiek, aby súčet ich škaredostí po skrášlení bol čo najmenší a aby sa po nich dalo dostať od každého záhonu ku každému. Je zaručené, že po pôvodných cestičkách sa dá dostať od každého ku každému. Skrášliť môžete každú cestičku ľubovoľne veľa krát, pričom za každé skrášlenie cestičky \(i\) zaplatíte \(c_i\) peňazí. Najviac môžete minúť \(S\) peňazí. Je povolené, aby škaredosť cestičky dosiahla 0 alebo aj záporné číslo.

Formát vstupu

Prvý riadok obsahuje dve kladné celé čísla \(n\) a \(m\) oddelené medzerou, označujúce počet záhonov a počet cestičiek. Záhony číslujeme od \(0\) do \(n-1\) a cestičky od \(0\) do \(m-1\).

Nasleduje \(m\) riadkov popisujúcich cestičky. Riadok \(i+1\) obsahuje v tomto poradí štyri čísla \(a_i\), \(b_i\), \(c_i\), \(w_i\) (\(0 \leq a_i, b_i < n\), \(a_i \neq b_i\), \(1 \leq c_i, w_i \leq 10^9\)). To značí, že cestička \(i\), so škaredosťou \(w_i\) a cenou skrášlenia \(c_i\), spája záhony \(a_i\) a \(b_i\). Medzi dvoma záhonmi môže ísť viacero cestičiek.

Posledný riadok obsahuje číslo \(S\) (\(0 \leq S \leq 10^9\)), počet Adamových peňazí.

Formát výstupu

Na prvom riadku vypíšte číslo \(K\) – súčet škaredostí vybraných ciest po skrášlení.

Potom vypíšte \(n-1\) riadkov. V každom riadku vypíšte dve čísla \(x\), \(v_x\), ktoré označujú, že cesta \(x\) je medzi vybranými a po skrášlení má škaredosť \(v_x\).

Cestičky môžete vypísať v ľubovoľnom poradí. Ak je riešení viacero, vypíšte ľubovoľné z nich.

Obmedzenia

Sú \(4\) sady vstupov po \(2\) body. Platia v nich nasledovné dodatočné obmedzenia:

Sada	\(1\)	\(2\)	\(3\)	\(4\)
\(1 \leq n \leq\)	\(10^5\)	\(300\)	\(10^4\)	\(10^5\)
\(1 \leq m \leq\)	\(10^5\)	\(300\)	\(10^4\)	\(10^5\)
\(1 \leq c_i \leq\)	\(1\)	\(10^9\)	\(10^9\)	\(10^9\)

Príklad

Input:

Output:

Input:

Output:

5
2 0
1 5

V prvom rade si treba uvedomiť, že v optimálnom riešení sa nám oplatí krášliť vždy iba jednu cestičku. Ak by sme krášlili viacero, mohli by sme miesto toho o rovnako veľa skrášlť najlacnejšiu z nich a určite by nám na to vyšli peniaze.

Môžeme teda skúšať možnosti, ktorá cestička to bude. Vždy si vyberieme jednu cestičku a skrášlime ju najviac ako vieme. S touto úpravou nám už zostáva iba vybrať cestičky s najmenšou škaredosťou. To znamená nájsť najlacnejšiu kostru grafu.

Iná možnosť je hľadať najlacnejšiu kostru, ktorá navyše obsahuje danú cestičku (bez úpravy škaredosti).

Najlacnejšia kostra sa dá nájsť v \(O(m\log n)\). To musíme spraviť pre každú hranu, čím dostávame časovú zložitosť \(O(m^2\log n)\). Pamäťová zložitosť je \(O(m)\).

#include <bits/stdc++.h>
using namespace std;

struct Edge
{
    int a;
    int b;
    int c;
    int w;
    int id;
};

vector<vector<Edge>> kostra(vector<vector<Edge>> G)
{
    int n = G.size();

    struct GreaterWeight
    {
        bool operator()(Edge e1, Edge e2)
        {
            return e1.w > e2.w;
        }
    };
    priority_queue<Edge, vector<Edge>, GreaterWeight> Q;

    vector<vector<Edge>> kostra(n);

    vector<bool> added(n, false);
    added[0] = true;
    for (Edge e : G[0])
        Q.push(e);
    while (Q.size())
    {
        Edge e = Q.top();
        Q.pop();
        if (added[e.b])
            continue;
        kostra[e.a].push_back(e);
        added[e.b] = true;
        for (Edge e1 : G[e.b])
            Q.push(e1);
    }
    return kostra;
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<Edge> all_edges;
    for (int i = 0; i < m; i++)
    {
        int a, b, c, w;
        cin >> a >> b >> c >> w;
        all_edges.push_back({a, b, c, w, i});
    }
    int S;
    cin >> S;

    long long best_score = LONG_LONG_MAX;
    vector<Edge> best_edges;

    for (int i = 0; i < m; i++)
    {
        vector<vector<Edge>> G(n);
        for (int j = 0; j < m; j++)
        {
            Edge e = all_edges[j];
            if (i == j)
                e.w -= S / e.c;
            Edge oposite = e;
            swap(oposite.a, oposite.b);
            G[e.a].push_back(e);
            G[oposite.a].push_back(oposite);
        }
        vector<vector<Edge>> K = kostra(G);
        vector<Edge> edges;
        long long nespokojnost = 0;
        for (auto x : K)
            for (Edge e : x)
            {
                edges.push_back(e);
                nespokojnost += e.w;
            }

        if (nespokojnost < best_score)
        {
            best_score = nespokojnost;
            best_edges = edges;
        }
    }
    cout << best_score << "\n";
    for (Edge e : best_edges)
        cout << e.id << " " << e.w << "\n";
}

Lepšie riešenie

Povedzme, že sme si zvolili hranu ktorú skúsime skrášliť a chceme nájsť najlacnejšiu kostru ktorá ju obsahuje. Dá sa ukázať, že takúto kostru vieme dostať z najlacnejšej kostry (celkovej) vymenením najviac jednej hrany.

Najlacnejšiu kostru vieme nájsť tak, že postupne pridávame vždy najlacnejšiu hranu ktorá spojí vrcholy, ktoré ešte nie sú v jednom komponente. Najlacnejšiu kostru s nejakou konkrétnou hranou nájdeme podobne, len ešte na začiatku hneď pridáme túto hranu. Pozrime sa, ako sa tieto kostry budú líšiť po každom kroku.

Začíname s dvoma prázdnymi grafmi \(A\) a \(B\). Do \(B\) ešte pridáme hranu medzi vrcholmi \(u\) a \(v\). V prvých niekoľkých krokoch sa budú líšiť iba v tejto hrane. To tiež znamená, že tieto grafy budú tvorené rovnakými komponentmi, až na to, že \(A\) bude mať \(u\), \(v\) v dvoch rôznych komponentoch a \(B\) ich bude mať spojené. Rozdiel nastane, až keď sa rozhodneme pridať hranu medzi vrcholmi, ktoré sú v jednom grafe v rôznych komponentoch a v duhom v rovnakom. To nutne musí byť hrana, ktorá v \(A\) spája komponenty obsahujúce \(u\) a \(v\), keďže všetky ostatné komponenty sú rovnaké. Keď túto hranu pridáme do \(A\), dosiahneme úplne rovnaké komponenty (tým aké vrcholy obsahujú) v \(A\) aj \(B\). Preto každá ďalšia pridaná hrana do \(A\) aj \(B\) bude rovnaká. To znamená, že výsledné kostry budú rovnaké, okrem hrany, ktorú sme na začiatku pridali do \(B\) a jednej hrany ktorú sme pridali do \(A\).

Môžeme teda použiť postup, že najprv nájdeme celkovú najlacnejšiu kostru a potom skúšame, ktorú hranu chceme skrášliť. Túto hranu pridáme ku kostre a jednu hranu z nej dáme preč. Spravíme to tak, aby sme získali najlacnejšiu kostru s touto hranou.

Hrana, ktorú odstránime, musí byť nejaká hrana na ceste medzi tými vrcholmi, kam pridávame hranu, inak by vznikol cyklus. Môže to byť ľubovoľná z nich. Najlepšie riešenie dostaneme, ak odstránime najškaredšiu z nich. Zatiaľ to spravíme tak, že prejdeme postupne všetky hrany na tejto ceste a nájdeme maximum.

Nájsť na začiatku najlacnejšiu kostru nám trvá \(O(m\log n)\). Potom pre každú hranu potrebujeme prejsť cestu medzi dvoma vrcholmi v kostre, čo môže trvať \(O(n)\). Z toho dostávame časovú zložitosť \(O(nm)\). Pamäťová zložitosť je znova \(O(m)\).

#include <bits/stdc++.h>
using namespace std;

struct Edge
{
    int a;
    int b;
    int c;
    int w;
    int id;
};

vector<vector<Edge>> kostra(vector<vector<Edge>> G)
{
    int n = G.size();

    struct GreaterWeight
    {
        bool operator()(Edge e1, Edge e2)
        {
            return e1.w > e2.w;
        }
    };
    priority_queue<Edge, vector<Edge>, GreaterWeight> Q;

    vector<vector<Edge>> kostra(n);

    vector<bool> added(n, false);
    added[0] = true;
    for (Edge e : G[0])
        Q.push(e);
    while (Q.size())
    {
        Edge e = Q.top();
        Q.pop();
        if (added[e.b])
            continue;
        kostra[e.a].push_back(e);
        added[e.b] = true;
        for (Edge e1 : G[e.b])
            Q.push(e1);
    }
    return kostra;
}

struct MaxPath
{
    vector<Edge> hore;
    vector<int> depth;
    int n;

    Edge max_weight(Edge e1, Edge e2)
    {
        if (e2.w > e1.w)
            return e2;
        else
            return e1;
    }

    void dfs_depth(vector<vector<Edge>> &tree, int i, int d = 0)
    {
        depth[i] = d;
        for (Edge e : tree[i])
            dfs_depth(tree, e.b, d + 1);
    }

    MaxPath(vector<vector<Edge>> &tree)
    {
        n = tree.size();
        hore.resize(n, {-1, 0, 0, 0, 0});
        for (auto x : tree)
            for (Edge e : x)
                hore[e.b] = e;
        depth.resize(n);
        dfs_depth(tree, 0);
    }

    Edge find_max(int a, int b)
    {
        Edge max_edge = {0, 0, 0, 0, 0};
        if (depth[a] > depth[b])
            swap(a, b);

        while (depth[b] > depth[a])
        {
            max_edge = max_weight(max_edge, hore[b]);
            b = hore[b].a;
        }
        while (a != b)
        {
            max_edge = max_weight(max_edge, hore[a]);
            a = hore[a].a;
            max_edge = max_weight(max_edge, hore[b]);
            b = hore[b].a;
        }
        return max_edge;
    }
};

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<Edge>> G(n);
    vector<Edge> all_edges;
    for (int i = 0; i < m; i++)
    {
        int a, b, c, w;
        cin >> a >> b >> c >> w;
        all_edges.push_back({a, b, c, w, i});
        G[a].push_back({a, b, c, w, i});
        G[b].push_back({b, a, c, w, i});
    }
    int S;
    cin >> S;

    vector<vector<Edge>> K = kostra(G);
    long long nespokojnost = 0;
    for (auto x : K)
        for (Edge e : x)
            nespokojnost += e.w;

    MaxPath max_path(K);
    long long best = nespokojnost;
    Edge to_remove;
    Edge to_add;
    for (Edge e : all_edges)
    {
        Edge worst = max_path.find_max(e.a, e.b);
        long long result = nespokojnost - worst.w + e.w - S / e.c;
        if (result <= best)
        {
            best = result;
            to_remove = worst;
            to_add = e;
        }
    }
    cout << best << "\n";
    for (auto x : K)
        for (Edge e : x)
        {
            if (e.id == to_remove.id)
                continue;
            cout << e.id << " " << e.w << "\n";
        }
    cout << to_add.id << " " << to_add.w - S / to_add.c << "\n";
}

Vzorové riešenie

Zlepšiť vieme hľadanie maximálnej hrany na ceste v strome. Začneme tým, že si ho zakoreníme v nejakom ľubovoľnom vrchole. Potom si pre každý vrchol predpočítame skoky o \(1, 2, 4, 8, \dots\) hore, tak ako keď hľadáme najnižšieho spoločného predka. Pre tieto skoky si okrem toho, na akom vrchole skončíme, pamätáme aj najlacnejšiu hranu na ceste ktorú sme preskočili. To vieme jednoducho vypočítať dynamikou od koreňa k listom: skok o \(2k\) je ako skok o \(k\) a potom ešte raz o \(k\) od vrchola na ktorom pristaneme. Okrem toho si potrebujeme vypočítať hĺbku každého vrchola.

Maximálnu hranu na ceste medzi dvoma vrcholmi nájdeme tak, že najprv nájdeme ich najnižšieho spoločného predka. Na to použijeme skoky ktoré sme si predpočítali. Najprv z vrchola s väčšou hĺbkou preskáčeme na vrchol s rovnakou hĺbkou ako druhý vrchol, na čo nám postačí najviac \(\log n\) skokov. Potom binárne vyhľadáme najnižšieho spoločného predka: ak skok z oboch vrcholov pristane na rovnakom vrchole sme vysoko, ak na rôznych sme nízko.

Už sa stačí pozrieť na to, ktoré skoky sme použili aby sme sa dostali od každého z vrcholov k ich spoločnému predkovi. Z týchto skokov zoberieme maximum, čím dostaneme maximálnu hranu na celej ceste.

Takto nám stačí vypočítať najlacnejšiu kostru len raz na začiatku v čase \(O(m\log n)\). Potom si vypočítame skoky z každého vrchola. Každý skok vypočítame v konštantom čase a skokov je najviac \(n\log n\). Následne pre každú hranu vieme nájsť maximálnu (najškaredšiu) hranu na vymenenie v čase \(O(\log n)\). Celkovo má toto riešenie časovú zložitosť \(O(m\log n)\). Pamäťová zložitosť je \(O(m + n\log n)\) keďže si musíme navyše pamätať všetky skoky.

#include <bits/stdc++.h>
using namespace std;

struct Edge
{
    int a;
    int b;
    int c;
    int w;
    int id;
};

vector<vector<Edge>> kostra(vector<vector<Edge>> G)
{
    int n = G.size();

    struct GreaterWeight
    {
        bool operator()(Edge e1, Edge e2)
        {
            return e1.w > e2.w;
        }
    };
    priority_queue<Edge, vector<Edge>, GreaterWeight> Q;

    vector<vector<Edge>> kostra(n);

    vector<bool> added(n, false);
    added[0] = true;
    for (Edge e : G[0])
        Q.push(e);
    while (Q.size())
    {
        Edge e = Q.top();
        Q.pop();
        if (added[e.b])
            continue;
        kostra[e.a].push_back(e);
        added[e.b] = true;
        for (Edge e1 : G[e.b])
            Q.push(e1);
    }
    return kostra;
}

struct Lca
{
    struct Jump
    {
        int to;
        Edge max_edge;
    };

    vector<vector<Jump>> jumps;
    vector<int> depth;
    int n;

    Edge max_weight(Edge e1, Edge e2)
    {
        if (e2.w > e1.w)
            return e2;
        else
            return e1;
    }

    void dfs_init(vector<vector<Edge>> &tree, int i, int d = 0, Jump up = {-1, {}})
    {
        depth[i] = d;
        if (up.to != -1)
        {
            jumps[i].push_back(up);
            for (int lvl = 0;; lvl++)
            {
                int next = jumps[i][lvl].to;
                if (lvl >= jumps[next].size())
                    break;
                Edge max_edge = max_weight(jumps[i][lvl].max_edge, jumps[next][lvl].max_edge);
                jumps[i].push_back({jumps[next][lvl].to, max_edge});
            }
        }

        for (Edge e : tree[i])
            dfs_init(tree, e.b, d + 1, {i, e});
    }

    Lca(vector<vector<Edge>> &tree)
    {
        n = tree.size();
        jumps.resize(n);
        depth.resize(n);
        dfs_init(tree, 0);
    }

    Edge find_max(int a, int b)
    {
        Edge max_edge = {0, 0, 0, 0, 0};
        if (depth[a] > depth[b])
            swap(a, b);

        for (int i = jumps[b].size() - 1; i >= 0; i--)
        {
            if (i >= jumps[b].size())
                continue;
            if (depth[jumps[b][i].to] < depth[a])
                continue;
            max_edge = max_weight(max_edge, jumps[b][i].max_edge);
            b = jumps[b][i].to;
        }

        if (a == b)
            return max_edge;

        for (int i = jumps[a].size() - 1; i >= 0; i--)
        {
            if (i >= jumps[a].size())
                continue;
            if (jumps[a][i].to == jumps[b][i].to)
                continue;
            max_edge = max_weight(max_edge, jumps[a][i].max_edge);
            a = jumps[a][i].to;
            max_edge = max_weight(max_edge, jumps[b][i].max_edge);
            b = jumps[b][i].to;
        }
        max_edge = max_weight(max_edge, jumps[a][0].max_edge);
        max_edge = max_weight(max_edge, jumps[b][0].max_edge);
        return max_edge;
    }
};

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<Edge>> G(n);
    vector<Edge> all_edges;
    for (int i = 0; i < m; i++)
    {
        int a, b, c, w;
        cin >> a >> b >> c >> w;
        all_edges.push_back({a, b, c, w, i});
        G[a].push_back({a, b, c, w, i});
        G[b].push_back({b, a, c, w, i});
    }
    int S;
    cin >> S;

    vector<vector<Edge>> K = kostra(G);
    long long nespokojnost = 0;
    for (auto x : K)
        for (Edge e : x)
            nespokojnost += e.w;

    Lca lca(K);
    long long best = nespokojnost;
    Edge to_remove;
    Edge to_add;
    for (Edge e : all_edges)
    {
        Edge worst = lca.find_max(e.a, e.b);
        long long result = nespokojnost - worst.w + e.w - S / e.c;
        if (result <= best)
        {
            best = result;
            to_remove = worst;
            to_add = e;
        }
    }
    cout << best << "\n";
    for (auto x : K)
        for (Edge e : x)
        {
            if (e.id == to_remove.id)
                continue;
            cout << e.id << " " << e.w << "\n";
        }
    cout << to_add.id << " " << to_add.w - S / to_add.c << "\n";
}

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ť.

7. Krášlenie cestičiek vzorové riešenie