[PA 2006] Żuczki

Dumel · Post autor: **Dumel** » 11 sie 2009, o 20:56

zrobiłem zadanie Żuczki z PA 2006 ( ... con=PA2006) i nie mam pomysłu jak dostatecznie usprawnić mój algorytm:

moje rozwiązanie:

#include<iostream>
#include <vector.h>
#include <queue.h>

enum COLOR {WHITE, GREY, BLACK};
void BFS(vector< vector<int> > &Adj, int s, vector<int> &d);
int max(int x, int y);
int min(int x, int y);

using namespace std;

main()
{
        ios_base::sync_with_stdio(0);
        int n, m;
        cin>>n>>m;
        int a,b;
        vector< vector<int> > Adj(n);
        for(int i(0); i<m; ++i)
        {
                cin>>a>>b;
                Adj[a-1].push_back(b-1);
                Adj[b-1].push_back(a-1);

        }
        vector<int> domek;
        int k;
        cin>>k;
        for(int i(0); i<k; ++i)
        {
                cin>>a;
                domek.push_back(a-1);
        }
        vector<int> d(n);
        int wynik=n+2;
        bool test;
        int j;
        int tmp;
        for(int i(0); i<n; ++i)
        {
                BFS(Adj, i, d);
                tmp=d[domek[0]];
                j=1;
                test=true;
                while(test && j<k)
                {
                        if((d[domek[j]]-d[domek[0]])%2==0)
                                tmp=max(tmp,d[j]);
                        else
                                test=false;
                        ++j;
                }
                if(test==true) wynik=min(wynik,tmp);
        }
        if(wynik==n+2) cout<<"NIE";
        else           cout<<wynik;
        
        return 0;
}
//---------------------------------------------------------------------------
/*
0,1,2,...,n-1 - wierzcholki grafu
Adj- listy sąsiedztwa
s-zrodlo
pi-poprzednicy na najkrotszej sciezce z s       -wczesniej okreslona liczba elementow
d- odleglosc od s                               /
*/
void BFS(vector< vector<int> > &Adj, int s, vector<int> &d)
{
        int n=Adj.size();
        vector<COLOR> color(n, WHITE);  //stan wierzcholka w czasie przeszukiwania grafu
        for(int i(0); i<n; ++i)
                d[i]=-1;


        d[s]=0;
        queue<int> Q;
        Q.push(s);
        int u;

        while(!Q.empty())
        {
                u=Q.front();
                Q.pop();
                for(int i(0); i<Adj[u].size();++i)
                {
                        if(color[ Adj[u][i] ]==WHITE)
                        {
                                color[ Adj[u][i] ]=GREY;
                                d[ Adj[u][i] ] = d[u]+1;
                                Q.push(Adj[u][i]);
                        }
                        color[u]=BLACK;
                }
        }

}
//---------------------------------------------------
int max(int x, int y)
{
        if(x>=y)return(x);
        else    return(y);
}
//---------------------------------------------------
int min(int x, int y)
{
        if(x<=y)return(x);
        else    return(y);
}

wywołuje BFSa dla każdego wierzchołka i sprawdzam czy żuczki mogą tam się spotkać. graf wejściowy jest drzewem więc długość każdej drogi z a do b to długość najkrótszej drogi+dowolna liczba parzysta co pozwala mi wyelimonować niektóre wierzchołki. jeżeli żuczki mogą się spotkać w danym wierzchołku (więc odległości domków od tego wierzchołka są tej samej parzystości) to wiadomo- spotkają się tam najwcześniej po upływie czasu który poświęci najdalej oddalony żuczek na dotarcie do tego wierzchołka. licze minimum i mam wynik.
zawsze \(\displaystyle{ m=n-1}\) więc algorytm działa w czasie \(\displaystyle{ O(n^2)}\). jak go usprawnić? pewnie potrzebny jest dużo sprytniejszy algorytm...

paladin · Post autor: **paladin** » 12 sie 2009, o 13:20

Najpierw pomalujmy sobie drzewo dwoma kolorami w sposób klasyczny (wierzchołki czarne mają tylko białych sąsiadów, białe tylko czarnych sąsiadów). Jeśli nie wszystkie żuczki okupują wierzchołki o tym samym kolorze, to nigdy się nie spotkają - po każdym ruchu będą na wierzchołkach różnych kolorów.

OK, sprawdziliśmy i tak nie jest. Jak sam słusznie zauważyłeś, trzeba po prostu znaleźć dwa najbardziej od siebie odległe żuczki. Robimy tak: bierzemy jakikolwiek wierzchołek \(\displaystyle{ a}\) z żuczkiem i zapuszczamy od niego BFS-a, znajdując wierzchołek \(\displaystyle{ u}\) z żuczkiem najbardziej odległy od \(\displaystyle{ a}\) (można wybrać dowolny z najdalszych). Teraz zapuszczamy BFS-a po raz drugi od wierzchołka \(\displaystyle{ u}\), znajdując wierzchołek \(\displaystyle{ v}\) z żuczkiem najbardziej odległy od \(\displaystyle{ u}\). Ścieżka \(\displaystyle{ u - v}\) będzie poszukiwaną najdłuższą ścieżką. Złożoność taka jak w sumie trzy BFS-y, czyli liniowa.

Dobrze, ale dlaczego \(\displaystyle{ u - v}\) jest najdłuższą ścieżką? Wyobraźmy sobie drzewo ukorzenione w \(\displaystyle{ a}\). Załóżmy, że jest jakaś inna, dłuższa ścieżka. Jeśli nie przecina ona ścieżki \(\displaystyle{ u - v}\), to znajdujemy jej najwyższy punkt w tym drzewie, i część od tego punktu zmieniamy tak, żeby przeszła przez \(\displaystyle{ a}\) i \(\displaystyle{ u}\) - można łatwo pokazać, że to jej nie skróci. Mielibyśmy więc ścieżkę zaczynającą się w \(\displaystyle{ u}\) dłuższą niż \(\displaystyle{ u - v}\), co jest niemożliwe.
Jeśli inna najdłuższa ścieżka przecina \(\displaystyle{ u - v}\), to nie może kończyć się w \(\displaystyle{ u}\), z podobnych powodów. Zatem opuszcza ścieżkę \(\displaystyle{ u - v}\) przed wierzchołkiem \(\displaystyle{ u}\) - znowu można łatwo pokazać, że gdyby do niego dotarła, byłaby nie krótsza.

Jest to wariant dość znanego algorytmu na szukanie średnicy drzewa.
Można też robić całe zadanie inaczej (ja tak robiłem) - obrywać kolejne liście, symulując tym samym ruch żuczków. Jeśli zrobimy to sprytnie (oberwij liścia, zmniejsz stopień jego rodzica, jeśli jest 1, wrzuć go na kolejkę do oberwania), w czasie liniowym znikną wszystkie i zostanie tylko wierzchołek, w którym żuczki się spotkają.

Dumel · Post autor: **Dumel** » 12 sie 2009, o 13:49

dzięki za pomoc

Jest to wariant dość znanego algorytmu na szukanie średnicy drzewa.
Można też robić całe zadanie inaczej (ja tak robiłem) - obrywać kolejne liście, symulując tym samym ruch żuczków. Jeśli zrobimy to sprytnie (oberwij liścia, zmniejsz stopień jego rodzica, jeśli jest 1, wrzuć go na kolejkę do oberwania), w czasie liniowym znikną wszystkie i zostanie tylko wierzchołek, w którym żuczki się spotkają.

troche czytałem o czymś takim ostatnio (nie o algorytmie tylko zagadnieniu) i nawet po napisaniu tego posta zacząłem sie zastanawiać czy może pójdzie z tego ale nie mialem konkretnych pomysłów. czy to nie jest poprostu wyszukiwanie centra w (pod?)drzewie? (może to sie teraz inaczej nazywa bo czytałem o tym w starej książce w której jest troche dziwna terminologia ). Jeśli tak to jak wyjdą dwa centra to bierzemy dowolne z nich?

paladin · Post autor: **paladin** » 12 sie 2009, o 13:52

Oj, ale ja nie rozumiem terminologii w takim razie. Jak definiujesz centrum drzewa?

Dumel · Post autor: **Dumel** » 12 sie 2009, o 13:58

tak myślałem że w tej książce jest już jakaś przestarzała.
centrum to taki wierzchołek którego maksymalna odległość od innego wierzchołka jest minimalna. Drzewo ma jedno lub 2 centra. Jeśli 2 to są one połączone krawędzią. Np. w grafie przykładowym z treści zadania są dwa centra: 2 i 4.
Centra można wyznaczać właśnie przez wywalanie liści aż zostanie 1 lub 2 wierzchołki.

paladin · Post autor: **paladin** » 12 sie 2009, o 14:13

Aha, to ja nie skojarzyłem. No cóż, w tym zadaniu po prostu nie może być dwóch centrów - widzisz, dlaczego?

Dumel · Post autor: **Dumel** » 12 sie 2009, o 14:31

już wiem
czyli ten Twój sposób to tak właściwie wyszukiwanie centra w drzewie ukorzenionym w domku żuczka i uciętym tak aby początkowo wszystkie liście były domkami żuczków
ta metoda bardziej mi sie podoba od tej pierwszej i jej poprawność jest bardziej intuicyjna-- 12 sierpnia 2009, 14:48 --a jakby dany graf nie musiał być drzewem dałoby sie to w przyzwoitej zlozonosci za pomoca prostych algorytmów zrobic?

paladin · Post autor: **paladin** » 12 sie 2009, o 17:59

Ale policzyć średnicę/centrum grafu czy rozwiązać zadanie o żuczkach?
Nie znam (i mam wątpliwości, czy w ogóle jest znana) metoda policzenia średnicy grafu szybciej niż O(VE).
Natomiast z żuczkami trzeba uważać jeszcze bardziej - nie każdy graf jest dwukolorowalny i może być tak, że żuczki mogą się spotkać, ale nie wolno im w tym celu użyć najkrótszej ścieżki. Da się zrobić to zadanie modyfikując nieco Twoją pierwotną metodę - dla każdego potencjalnego punktu spotkania sprawdzić, w jakiej najkrótszej parzystej oraz w jakiej najkrótszej nieparzystej liczbie ruchów może do niego dojść każdy żuczek. Złożoność wciąż O(VE).

Dumel · Post autor: **Dumel** » 12 sie 2009, o 18:46

mógłbyś mi pomóc jeszcze w jednym? właściwie nie chodzi mi o ściśle rozwiązanie tylko mam konkretne pytanie do tego zadania: ... n=PA2002-2. Czy to nie ogranicza sie czasem poprostu do znalezienia minimalnego drzewa rozpinającego i wyszukania w nim krawedzi o najwiekszej wadze? Pamiętam z Cormena dowód poprawności algorytmu Prima i na moje oko dowód jego poprawności do tego problemu bedzie praktycznie identyczny ale z drugiej strony dziwne by to bylo gdyby dali w 3. rundzie PA takie zadanie. Dla Ciebie to pewnie 3 sekundy roboty a nie chciałbym sie zabierac za kodowanie zupełnie złego rozwiązania.

-- 12 sierpnia 2009, 19:05 --

sorki za fatygę jeśli już masz mnie dosyć to nie odpowiadaj . tak przeglądam sobie te zadania i mógłbyś mnie upewnić czy w tym: ... con=PA2005 wystarczy znaleźć wierzchołki o nieparzystym stopniu: \(\displaystyle{ a_1,a_2,...,a_{2k}}\), dorzucić do grafu krawędzie \(\displaystyle{ a_{2i+1}-a_{2i+2}}\) dla i=0,1,...,k-1, znaleźć cykle Eulera wszystkich składowych i rozbić je na ścieżki w miejscach gdzie występują wcześniej dorzucone krawedzie?-- 12 sierpnia 2009, 19:07 --oczywiście od października będę Ci codziennie mówił na korytarzu dzień dobry

paladin · Post autor: **paladin** » 13 sie 2009, o 00:01

Dumel pisze:mógłbyś mi pomóc jeszcze w jednym? właściwie nie chodzi mi o ściśle rozwiązanie tylko mam konkretne pytanie do tego zadania: ... n=PA2002-2. Czy to nie ogranicza sie czasem poprostu do znalezienia minimalnego drzewa rozpinającego i wyszukania w nim krawedzi o najwiekszej wadze?

Trzeba znaleźć takie drzewo rozpinające, które ma minimalną największą krawędź. Nie ma to nic wspólnego z minimalnym drzewem rozpinającym. Najłatwiej zrobić to, wyszukując binarnie koszt - zgadujemy, że ma być równy \(\displaystyle{ s}\), wycinamy na chwilę z grafu wszystkie krawędzie droższe niż \(\displaystyle{ s}\) i patrzymy, czy ma on jakieś drzewo rozpinające (czyli po prostu czy jest spójny). Jeśli się da, to próbujemy z mniejszym kosztem, jeśli się nie da - z większym. Złożoność \(\displaystyle{ O(m \log A)}\), gdzie \(\displaystyle{ A}\) jest sumą kosztów wszystkich autostrad.

sorki za fatygę jeśli już masz mnie dosyć to nie odpowiadaj . tak przeglądam sobie te zadania i mógłbyś mnie upewnić czy w tym: ... con=PA2005 wystarczy znaleźć wierzchołki o nieparzystym stopniu: \(\displaystyle{ a_1,a_2,...,a_{2k}}\), dorzucić do grafu krawędzie \(\displaystyle{ a_{2i+1}-a_{2i+2}}\) dla i=0,1,...,k-1, znaleźć cykle Eulera wszystkich składowych i rozbić je na ścieżki w miejscach gdzie występują wcześniej dorzucone krawedzie?

Dokładnie tak. Można też dorzucić jeden sztuczny wierzchołek i połączyć go ze wszystkimi \(\displaystyle{ a_j}\) - mnie osobiście się tak łatwiej pisało, ale to rzecz gustu.

oczywiście od października będę Ci codziennie mówił na korytarzu dzień dobry

Robiąc u nas Algorytmy i Struktury Danych masz sporą szansę oberwać tym ostatnim zadaniem jako jednym z wielu do napisania, i obawiam się, że to moja sprawka

Dumel · Post autor: **Dumel** » 13 sie 2009, o 09:55

paladin pisze: Trzeba znaleźć takie drzewo rozpinające, które ma minimalną największą krawędź. Nie ma to nic wspólnego z minimalnym drzewem rozpinającym. Najłatwiej zrobić to, wyszukując binarnie koszt - zgadujemy, że ma być równy \(\displaystyle{ s}\), wycinamy na chwilę z grafu wszystkie krawędzie droższe niż \(\displaystyle{ s}\) i patrzymy, czy ma on jakieś drzewo rozpinające (czyli po prostu czy jest spójny). Jeśli się da, to próbujemy z mniejszym kosztem, jeśli się nie da - z większym. Złożoność \(\displaystyle{ O(m \log A)}\), gdzie \(\displaystyle{ A}\) jest sumą kosztów wszystkich autostrad.

to chyba lepiej posortować koszty na początku i dalej puścić wyszukiwanie binarne to wtedy bedzie \(\displaystyle{ O(mlogm)}\)
nadal nie rozumiem dlaczego wyszukiwanie MST nie będzie tu działało. przecież jak mamy dwie rozłączne wierzchołkowo składowe \(\displaystyle{ A}\) i \(\displaystyle{ B}\) to musimy je połączyć krawędzią więc najlepiej wziąć tę o najmniejszej wadze, a wybór konkretnej krawędzi nie wpływa na dalsze tworzenie drzewa.

paladin · Post autor: **paladin** » 13 sie 2009, o 12:18

Dumel pisze:to chyba lepiej posortować koszty na początku i dalej puścić wyszukiwanie binarne to wtedy bedzie \(\displaystyle{ O(mlogm)}\)

Akurat tu różnica jest praktycznie żadna...

nadal nie rozumiem dlaczego wyszukiwanie MST nie będzie tu działało. przecież jak mamy dwie rozłączne wierzchołkowo składowe \(\displaystyle{ A}\) i \(\displaystyle{ B}\) to musimy je połączyć krawędzią więc najlepiej wziąć tę o najmniejszej wadze, a wybór konkretnej krawędzi nie wpływa na dalsze tworzenie drzewa.

...a tu masz absolutną rację. Tak to jest, jak się odpowiada bez myślenia.
Zwykły zachłanny algorytm wyszukiwania MST niejako przy okazji znajduje takie o minimalnej najdroższej krawędzi. Najlepiej to widać na algorytmie Kruskala, który działa dokładnie na zasadzie "posortuj krawędzie i dorzucaj od najtańszych, dopóki graf nie będzie spójny".