• 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

Object Storage Arubacloud
0 głosów
514 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 (91,190 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ź 311 wizyt
pytanie zadane 12 czerwca 2015 w C i C++ przez krecik1334 Maniak (58,390 p.)
0 głosów
1 odpowiedź 100 wizyt
+1 głos
0 odpowiedzi 308 wizyt

92,696 zapytań

141,607 odpowiedzi

320,114 komentarzy

62,055 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.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...