• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie trzęsienie ziemi Zdalne Warsztaty Olimpijskie Dla Juniorów 2022, MST

Aruba Cloud - Virtual Private Server VPS
0 głosów
759 wizyt
pytanie zadane 7 marca 2023 w C i C++ przez pasjonat_algorytmiki Pasjonat (19,540 p.)
edycja 7 marca 2023 przez pasjonat_algorytmiki

Mam takie zadanie: https://sio2.mimuw.edu.pl/c/zwo22/p/trz/ Wydaje mi się, że treść to zaimplementuj MST, napisałem kod, który się daje wrong answer w wszystkich testach oprócz przykładowego....

Wie ktoś może, gdzie jest błąd, co dziwne kod jest bardzo krótki. Korzystam z mojego ulubionego(wsumie jedynego jakiego znam, ale uznałem, że jest ulubiony bo bardzo lubię algorytm Dijkstry, a on wydaje się być podobny.....) algorytmu do szukania MST - algorytmu Prima.

Kod:

#include <iostream>
#include <vector>
#include <set>

using namespace std;

struct Krawedz
{
    int do_kogo;
    int cena;
};

struct Element_seta
{
    int wierzcholek;
    int cena;
    bool operator < (const Element_seta &element_seta) const
    {
        if (cena == element_seta.cena)
            return wierzcholek < element_seta.wierzcholek;
        return cena < element_seta.cena;
    }
};

int n = 0, m = 0, x = 0, y = 0, z = 0, wyn = 0;
vector<vector<Krawedz>> krawedzie;
set<Element_seta> S;
vector<int> dp;

int main()
{
    // Algorytm Prima, do wyznaczania MST.
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    dp.assign(n+1,-1);
    krawedzie.assign(n+1,{});
    for (int i = 0; i < m; ++i)
    {
        cin >> x >> y >> z;
        krawedzie[x].push_back({y,z});
        krawedzie[y].push_back({x,z});
    }

    S.insert({1,0});
    dp[1] = 0;
    while(!S.empty())
    {
        Element_seta spr = *S.begin();
        S.erase(spr);
        wyn += spr.cena;
        for (int i = 0; i < krawedzie[spr.wierzcholek].size(); ++i)
        {
            int wierz = krawedzie[spr.wierzcholek][i].do_kogo;
            if (dp[wierz] == -1 or krawedzie[spr.wierzcholek][i].cena < dp[wierz])
            {
                auto it = S.find({wierz, dp[wierz]});
                if (it != S.end())
                    S.erase(*it);
                dp[wierz] = krawedzie[spr.wierzcholek][i].cena;
                S.insert({wierz, dp[wierz]});
            }
        }
    }

    cout << wyn << '\n';

    return 0;
}

Dodam, że w sprawie MST, jestem kompletnym świeżakiem, jest to chyba dopiero drugie zadanie jakie robię na MST, pierwsze to było coś w stylu: zaimplementuj MST.

Z góry dziękuję za pomoc i poświęcony czas!

komentarz 7 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
mój algorytm daje za duże wyniki
komentarz 7 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Chyba źle rozumiem treść, bo wrzuciłem na sprawdzarkę do tego zadania co pierwsze robiłem na MST, i przechodzi
komentarz 7 marca 2023 przez Benek Szeryf (93,070 p.)

@pasjonat_algorytmiki, tak swoją drogą, czemu nie nazywasz zmiennych po angielsku?

komentarz 7 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Wsumie od zawsze używam polskich, a jeszcze mam dobre 4 lata startowania w OI, więc do tego czasu moja leniwość nie powinna przynieść negatywnych skutków. Ale to jest słuszna uwaga, będę musiał się przerzucić na angielskie. Ale mój angielski też nie jest jakiś niesamowity....
komentarz 7 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

@pasjonat_algorytmiki, 

nie kumam co tu się dzieje. Treść to na 99% zaimplementuj MST, a ten kod jak wklejam do innego zadania na MST działa xD A testy też są dobre, bo jest dużo setek na sio

1 odpowiedź

0 głosów
odpowiedź 7 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Już znalazłem błąd. Problem był taki, że nie miałem vectora visited, czy już dodałem ten wierzchołek do MST, i liczył niektóre wierzchołki po kilka razy. Wystarczyło dodać vector visited. W tym kodzie co pisałem w pierwszym zadaniu musiałem znaleźć wagę o największej krawędzi należącej do MST, więc ten błąd nie przeszkadzał...

Kod poprawiony dający już setkę z około 1/5 zapasu z dostępnego limitu na to zadanie na sio2:

#include <iostream>
#include <vector>
#include <set>

using namespace std;

struct Krawedz
{
    int do_kogo;
    int cena;
};

struct Element_seta
{
    int wierzcholek;
    int cena;
    bool operator < (const Element_seta &element_seta) const
    {
        if (cena == element_seta.cena)
            return wierzcholek < element_seta.wierzcholek;
        return cena < element_seta.cena;
    }
};

int n = 0, m = 0, x = 0, y = 0, z = 0, wyn = 0;
vector<vector<Krawedz>> krawedzie;
set<Element_seta> S;
vector<int> dp;
vector<bool> czy_bylismy;

int main()
{
    // Algorytm Prima, do wyznaczania MST.
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    czy_bylismy.assign(n+1,false);
    dp.assign(n+1,-1);
    krawedzie.assign(n+1,{});
    for (int i = 0; i < m; ++i)
    {
        cin >> x >> y >> z;
        krawedzie[x].push_back({y,z});
        krawedzie[y].push_back({x,z});
    }

    S.insert({1,0});
    dp[1] = 0;
    czy_bylismy[1] = true;
    while(!S.empty())
    {
        Element_seta spr = *S.begin();
        S.erase(spr);
        czy_bylismy[spr.wierzcholek] = true;
        wyn += spr.cena;
        for (int i = 0; i < krawedzie[spr.wierzcholek].size(); ++i)
        {
            int wierz = krawedzie[spr.wierzcholek][i].do_kogo;
            if (czy_bylismy[wierz] == true)
                continue;
            if (dp[wierz] == -1 or krawedzie[spr.wierzcholek][i].cena < dp[wierz])
            {
                auto it = S.find({wierz, dp[wierz]});
                if (it != S.end())
                    S.erase(*it);
                dp[wierz] = krawedzie[spr.wierzcholek][i].cena;
                S.insert({wierz, dp[wierz]});
            }
        }
    }

    cout << wyn;

    return 0;
}

 

komentarz 7 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
edycja 7 marca 2023 przez pasjonat_algorytmiki
ogólnie a propo MST, to dowiedziałem się o tej historii z biednym Czechem, który wymyślił algorytm Prima kilkanaście / dziesiąt lat wcześniej, ale go nikt nie zauważył... (O ile dobrze zrozumiałem tą historię) https://pl.wikipedia.org/wiki/Algorytm_Prima

Podobne pytania

0 głosów
1 odpowiedź 354 wizyt
pytanie zadane 12 czerwca 2015 w C i C++ przez krecik1334 Maniak (58,390 p.)
0 głosów
1 odpowiedź 134 wizyt
+1 głos
0 odpowiedzi 329 wizyt

93,334 zapytań

142,328 odpowiedzi

322,406 komentarzy

62,670 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj

Wprowadzenie do ITsec, tom 1 Wprowadzenie do ITsec, tom 2

Można już zamawiać dwa tomy książek o ITsec pt. "Wprowadzenie do bezpieczeństwa IT" - mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy aż 15% zniżki! Dziękujemy ekipie Sekuraka za fajny rabat dla naszej Społeczności!

...