[Biciklisti]

Prolaze mi svi primeri sem poslednjeg na koji mi izbacuje "sistemska greska ili memoriski limit".Inace zadatak sam radio rekurzivno i mislim da 10 primer puca zato sto se premasi stek memorija mada u toj funkciji imam samo dva integer-a ???
Da li je neko imao slicnih problema i da li je neko uopste ovaj zadatak radio rekurzijom(npr DFS-om).

PS
Nebi bilo lose ako neko ima taj primer da mi ga posalje (milospetkovic@gmail.com)

Pa mozes napisati iterativni DFS, namesto rekurzivni.

Evo ti kod:


// DFS procedura so eksplicitna upotreba na stack, namesto rekurzija.

#include "stdafx.h"
#include <stack>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

#define FOR(i, n) for (int i=0; i<n; i++)
#define FORR(i, a, b) for (int i=a; i<=b; i++)
#define MAXN 9
#define INF 10000


struct edge {
int v;
edge() {}
edge(int vv) { v = vv; }
};

vector <edge> g[MAXN];
vector <int> visited (MAXN);
int n, m;

void init()
{
n = 8; m = 9;
g[1].push_back(edge(2));
g[1].push_back(edge(3));
g[1].push_back(edge(4));
g[2].push_back(edge(6));
g[2].push_back(edge(5));
g[6].push_back(edge(5));
g[3].push_back(edge(7));
g[4].push_back(edge(5));
g[5].push_back(edge(8));
}

void dfs ()
{
stack <int> s;
vector <edge>::iterator it;
int v, w;
s.push(1);


while (!s.empty()) {
v = s.top();
s.pop();
visited[v] = 1;
cout << v << " ";

it = g[v].begin();

while (it != g[v].end()) {
w = it++->v;
if (!visited[w])
s.push(w);
}
}
cout << endl;
}

int main()
{
init();
dfs ();
return 0;
}

Hvala za kod,ali sam uradio zadatak izbacujuci jedan parametar iz rekurzije......
Pozz

Radio sam dfs-om ali mi 8. i 9. test primer padaju na vremenu. Ostali prolaze ispod 0.2 sekunde. Da li neko moze da mi da neki savet o tome kako da optimizujem algoritam ili da mi posalje neki od ova dva test primera? ???

Moze li neko poslati i meni 8 i 9? Ako su preveliki:
simjanoskiviktor@gmail.com

Ok, proslo je. Problem je u tome sta mislim da su ove dve test primere gresni. Kad sam smenio velicinu vektora iz 8000 na 8050, sve je bilo u redu.

Nemoj kriviti druge samo zato sto tvoj algoritam ne radi dobro. Sem toga sto sam proverio test primer, u mom kodu ja uzimam najvise 8000 i radi kako treba. Sve je bilo u redu jer si ti sigurno negde uzimas vise od 8000 elemenata.

Dobro ondak, izvinjavam se, ali ne bi mogao da zamisljim zasto bi usimao vise od 8000 elemanta.

Evo jos jedne metode kojom se moze raditi zadatak, mozda nekome pomogne.

Napisati funkciju koja je nalik dajkstrinom algoritmu. Znaci, F(5) racuna sva rastojanja od cvora 5, ali nema potrebe da trazi najkraca jer postoji samo jedan put od cvora 5 do ostalih.

Ako funkciju F pozovemo za bilo koji cvor P i sa S obelezimo najudaljeniji cvor od cvora P, tada ce udaljenost najdaljeg cvora od S biti resenje zadatka.

Mislim da se ovakvi problemi zovu "nalazenje precnika grafa", nisam siguran. Uglavnom, ideja je "obesiti" graf o bilo koji cvor, zatim ga obesiti o najdalji cvor od korena. U takvom drvetu (nakon dva "vesanja") koren mora biti pocetak najduzeg prostog puta.

Nadam se da je jasno...

Zadatak biciklisti me muci neko vrijeme...

Prvo sam mislio rjesit rekurzijom ali ne vjerujem da bi to proslo, ima slozenost vecu od O(n^2)... postoji li neki brži način da se rjesi ovaj zadatak...
bio bih zahvalan

U principu, zadatak moze da se resi u linearnom vremenu u zavisnosti od n. Naime, treba primetiti da taj put kojim se on krece je zapravo stablo. Od datog stabla napravis korensko (odnosno pretragu krenes od nekog cvora) i imas sledece mogucnosti
1) najduzi put prolazi kroz dati cvor, pa se levi i desni deo puta nalazi u nekom od podstabala koje izracunas
2) najduzi put se ceo nalazi u nekom od podstabala i to resis rekurzivno.

Znam da nije bas detaljno, ali ovo ti je pomoc, pa probaj da razradis. Ako ne uspes, javi se ;)

Pada mi na 3,5,8... pa ako mogu dobiti jedan od njih, ako moderatori sada mogu vidjeti test primjere

Nazalost, jos ne mogu :|

Evo ti mog predloga - koliko vidim onaj postovan code je tacno resenje, ako sam dobro shvatio autora, pa onda uzmes taj code, izgenerises neke random primere i proveris na kom ti pada. Sigurno ces u nekom momentu naci primer za koji ti ne radi. Eto, onda i ne moras da cekas modeatore ;)

Mislim da kod gore ne radi jer ne posmatra udaljenost dviju gradova

Prepravio sam sve moguce greskice i lijepo poslao...

Test 1 OK 0.01 s.
Test 2 OK 0 s.
Test 3 OK 0 s.
Test 4 OK 0.01 s.
Test 5 OK 0.01 s.
Test 6 OK 0.02 s.
Test 7 OK 0.01 s.
Test 8 OK 0.03 s.
Test 9 OK 0.02 s.
Test 10 OK 0.02 s.

Hvala ti na pomoci, nisam imao ideju upoce kako ga rjesiti...

Ima jos jedan (laksi) nacin:
1. uzmi bilo koju tocku A
2. nadji tocki A najudaljeniju tocku B
3. nadji tocki B najudaljeniju tocku C

Najdulji put u stablu je B -> C

Zasto je to tako ne znam, zguglajte negdje dokaz za to.

Ne znam gdje grijesim pa ako neko moze da pomogne

http://z-trening.com/submit.php?submit=7100349822&subm_code=1

testiraj ovo:
4
1 2 1
2 3 5
2 4 8

9 sto bi trebalo biti ok, ili grijesim

imam jedan problem ne znam do cega je, vjerovatno do mog kompajlera: program jedino radi ako postavim system("pause") na 24 liniji.

Primetio sam da program abortuje, i vreovatno je greska u dfs(). Inace, rezultat je 13 (2-3-4). Da bi nasao najduzu, nadji najduzu rutu polazeci od cvora 1. Ako se ta ruta yavrsava u cvoru A, sada nadji najduzu rutu polezeci od cvora A, i to je rezultat.
Mozda ce ti dfs() smetati (zbog rekuzije, pojesce memoriju steka), pa ti preporucujem da proguglas Dijkstru .
p.s. Sve ovo je vec receno na ovom forumu.
Da ne bi abortovao:
while(x < n && grad[x].a==u){....

Rijesio sam. Hvala