Speedrun - OIJ II etap

Question

Witam, mam pytanko odnośnie zadania speedrun z II etapu OIJ XIV. Trzeba tutaj użyć grafów, czy jest prostszy sposób? Mi udało się je zrobić na grafy, lecz w kilku testach mam przekroczenie czasu. Wydaje mi sie ze to przez tego dfs'a wywolywanego n razy.

zadanie: https://szkopul.edu.pl/problemset/problem/e0qogVe4A5ivK_pTdUXL39FV/site/?key=statement

kod:

#include <bits/stdc++.h>

#define x first
#define y second

#define INF 1e9 + 9

using namespace std;

void wczytaj(int n);
void dfs(int w, int cos);

pair <int, int> arr[100001];
bool vis[100001];
int minCos = INF;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;

    wczytaj(n);

    for (int i = 1; i <= n; i ++) {
        dfs(i, 0);
    }

    cout << minCos;
}

void wczytaj(int n) {
    for (int i = 1; i <= n; i ++) {
        cin >> arr[i].x;

        arr[i].y = i;
    }
}

void dfs(int w, int cos) {
    if (vis[w]) {
        minCos = min(minCos, cos);
        return;
    }

    vis[w] = 1;

    dfs(arr[w].x, cos + arr[w].y);

    vis[w] = 0;
}

 

Answer 1

Zadanie to klasyczne wyznaczanie cykli, podział na spójne składowe. Dzielisz graf na spójne składowe i dla każdej spójnej trzymasz min wyn, biorąc pod uwage, że zaczynasz z dowolnego wierzchołka z spójnej. I teraz jesli idziesz sobie tym DFS-em, to jeśli natkniesz się na wierzchołek który już jest w jakieś składowej, to tam nie idziesz, bo tylko pogorszy to wynik, bo musisz zrobić min_wyn_z_skladowej + wyn_z_sprawdzanej_skladowej. Teraz jest jedna pułapka a mianowicie, zauważ, że tak jak na rysunku dla każdej składowej liczysz min wyn, więc zawsze najbardziej opłaca ci się zacząc liczyć wynik dla składowej z tego wierzchołka do którego wchodzi cykl. (Rysunek). Więc O(n), bo każdy wierzchołek maksymalnie raz przetworzysz. Masz kod, który pisałem:

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

ll n = 0, wczytana_liczba = 0, cnt = 0, wyn = 0, min_wyn = 1e15+5;
vector<ll> rodzice;
vector<ll> numer_spojnej;

void dfs(ll v)
{
    numer_spojnej[v] = cnt;
    if (numer_spojnej[rodzice[v]] == cnt)
    {
        // Odtwarzamy wynik dla spojnej skladowej. Wauwaz, ze najmniejszy wynik musi zaczynac sie w numer_spojnej[rodzice[v]]
        int wierzcholek_docelowy = rodzice[v];
        int wierzcholek_spr = rodzice[v];
        while (true)
        {
            if (wierzcholek_spr == wierzcholek_docelowy && wyn != 0)
                break;
            wyn += wierzcholek_spr;
            wierzcholek_spr = rodzice[wierzcholek_spr];
        }
    }
    else if (numer_spojnej[rodzice[v]] == -1)
        dfs(rodzice[v]);
    else
    {
        wyn = 1e15+5+5;
        return;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    numer_spojnej.assign(n+1,-1);
    rodzice.push_back(0);
    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba;
        rodzice.push_back(wczytana_liczba);
    }

    for (int i = 1; i <= n; ++i)
    {
        if (numer_spojnej[i] == -1)
        {
            wyn = 0;
            dfs(i);
            min_wyn = min(min_wyn,wyn);
            cnt++;
        }
    }
    printf("%lld",min_wyn);

    return 0;
}

Spoko zadanie to zadanie bankiet z podajrze 2 etapu 2 OIG-a, łatwiejszy speedrun. I tez https://codeforces.com/problemset/problem/1020/B

Comments

btw. Bardzo dobre rozwiązanie jest na kanale OIJ, przez Pana Karola Pokorskiego. Ogólnie dużo zadań omówione jest na kanałach: OIJ, OKI, Wrocławskie Sparingi Informatyczne. Są też pliki tekstowe OIJ w przypadku OIJ-a, a w OI-a książeczki

https://www.youtube.com/watch?v=5zCYlIsHBkU&list=PLHydfZN9Vk9Rak9DSFSzzPxBoLjCoga5F&index=2