•rgrig
|
|
« : Ianuarie 18, 2005, 22:19:24 » |
|
Asta e a doua oara cand particip la usaco si rezultatul e jalnic: 1. la "sumset" am uitat sa iau modulo 1e+9 2. la volume am lucrat pe 32b 3. la "watchcow" am iesit din timp Problema "watchcow" a fost ceva nou - pt mine. As vrea sa stiu daca abordarea e proasta sau pur si simplu am implementat prost. Am facut:
S = multime vida de cicluri reprezentare prin liste de adiacenta (cu cate doua muchii orientate pt. fiecare din enunt) cat timp graf mai are muchii fa dfs si gaseste un ciclu C pentru fiecare ciclu X din multimea de cicluri S daca C il atinge pe X uneste C cu X; elimina pe X din S adauga pe C la X scrie unicul (?) ciclu ramas in S
multumesc, radu - nu rideti, n-am facut niciodata informatica in mod formal (i.e. la scoala)
|
|
|
Memorat
|
|
|
|
•rgrig
|
|
« Răspunde #1 : Ianuarie 18, 2005, 22:20:42 » |
|
oops, am omis:
ultima actiune din ciclul "cat timp" este "sterge muchiile lui C din graf"
|
|
|
Memorat
|
|
|
|
•silviug
|
|
« Răspunde #2 : Ianuarie 18, 2005, 23:01:48 » |
|
Salutare. Nu am avut rabdare sa vad ce face algoritmul tau. Deci voi trece direct la explicatii: problema se reduce la a gasi un ciclu eulerian intr-un graf orientat. Reamintesc ca prin ciclu eulerian intelegem ciclu care viziteaza fiecare muchie o singura data. Graful initial este neorientat dar il vom transforma usor intr-unul orientat inlocuind fiecare muchie cu doua muchii orientate opus. Avand graful nou format se face un DFS in care avem grija sa nu parcurgem o muchie de doua ori (in schimb se poate trece printr-un nod de mai multe ori!). Ciclul va fi format din toate nodurile atinse de DFS (cu tot cu repetitii!) scrise in ordine inversa. DFS-ul ar arata asa: DFS(nod) { pentru fiecare vecin X al lui nod { sterge muchia (nod, X) DFS(X) } ciclu(count) = nod; count = count + 1; }
Sper ca e clar, Silviu
|
|
|
Memorat
|
"Don't gain the world and lose your soul, wisdom is better than silver or gold." [Bob Marley - Jamaican reggae musician & singer (1945 - 1981)]
|
|
|
•rgrig
|
|
« Răspunde #3 : Ianuarie 19, 2005, 09:08:27 » |
|
Multumesc.
|
|
|
Memorat
|
|
|
|
•svalentin
|
|
« Răspunde #4 : Ianuarie 19, 2005, 14:14:05 » |
|
Dar ai grija in ce complexitate vezi vecinii nodului nod! adica daca vrei sa iti mearga rapid trebuie sa ii tii mine intr-o lista! ex: daca nodul 5 are 3 vecinii: 1 2 3; poti tine minte ca v[5]={3, 1, 2, 3} si ca sa nu ai probleme cu memoria lista o poti aloca dinamic Astfel vei avea o complexitate O(M) (M=nr de muchii)
Si inca ceva ce am observat: daca faci recursiv, chiar si cu lista dinamica, nu iti intra in timp un test (cel putin mie nu mi-a intrat)... de aceea poti sa iti implementezi propria stiva. Adica in loc sa apelezi DFS(X), bagi X in fata stivei, iar in programul principal ai un while (stiva nu e goala) ... Asta se intampla din cauza ca programului ii mai ia mai mult timp sa bage in stiva reala functia DFS, cu parametru X.. Si asa poti evita si probleme cu memoria (adica la USACO poti sa declari stiva ta global, unde ai 15M!)
|
|
|
Memorat
|
|
|
|
•silviug
|
|
« Răspunde #5 : Ianuarie 19, 2005, 20:54:00 » |
|
Ce bine le spune Vali.. ca un mare campion
|
|
|
Memorat
|
"Don't gain the world and lose your soul, wisdom is better than silver or gold." [Bob Marley - Jamaican reggae musician & singer (1945 - 1981)]
|
|
|
•rgrig
|
|
« Răspunde #6 : Ianuarie 20, 2005, 19:19:39 » |
|
Vad ca n-are nici o problema recursiv: cel mai mult dureaza 0.26s. Codul e aproape ca si pseudocodul: void dfs(int x) { while (!g[x].empty()) { int y = g[x].front(); g[x].pop_front(); dfs(y); } cycle.push_back(x+1); }
|
|
|
Memorat
|
|
|
|
•svalentin
|
|
« Răspunde #7 : Ianuarie 21, 2005, 11:08:06 » |
|
Poate din cauza ca ai folosit STL-ul iti merge mai bine ca mine... Asa am facut si eu, doar ca lista aia de muchii aveam eu grija de ea Aveam un vector int *m[nr de noduri] si pt fiecare element din vector ii alocam memorie cat gradul fiecarui nod * int, apoi puneam in vector (care acum este o matrice bidimensionala) lista de noduri vecine pt fiecare nod. Poate din cauza ca mai faceam aceste calcule in plus imi merge mai greu...
|
|
|
Memorat
|
|
|
|
•rgrig
|
|
« Răspunde #8 : Ianuarie 21, 2005, 12:30:40 » |
|
Nu prea cred ca e de la calculele astea. Cum "stergeai" muchiile? Eu tin lista de adiacenta intr-o lista inlantuita:
|
|
|
Memorat
|
|
|
|
•silviug
|
|
« Răspunde #9 : Ianuarie 21, 2005, 12:40:13 » |
|
Radule (probabil asa te cheama) ar fi marfa daca ai pune codul pe forum.. poate mai invata si baietii cate ceva (poate chiar si eu). STL stiu foarte putin dintre elevii din Romania si ar cam trebui sa inceapa sa invete.. Nu am vazut offtopic-ul tau despre angajare.. noi il asteptam Numa bine, Silviu
|
|
|
Memorat
|
"Don't gain the world and lose your soul, wisdom is better than silver or gold." [Bob Marley - Jamaican reggae musician & singer (1945 - 1981)]
|
|
|
•rgrig
|
|
« Răspunde #10 : Ianuarie 21, 2005, 13:02:22 » |
|
Asa ma cheama. Postul despre angajare este pus in "Off-topic". Probabil ca nu are un subject prea imbietor Asta e codul complet (plus cateva comentarii ca sa nu va mirati de niste lucruri care par nenecesare): #include <iostream> // for debug #include <fstream> #include <list> #include <vector> #include <algorithm> #include <iterator>
#define ALL(c) (c).begin(), (c).end()
using namespace std;
vector<list<int> > g; vector<int> cycle;
void dfs(int x) { while (!g[x].empty()) { int y = g[x].front(); g[x].pop_front(); dfs(y); } cycle.push_back(x+1); }
int main() { ifstream inf("watchcow.in"); ofstream outf("watchcow.out"); istream& in = inf; // for debug: just change inf to cin to work with console ostream& out = outf; // for debug: just change outf to cout to work with console
int N, M; in >> N >> M; g.resize(N); int i, j; int a, b; for (i = 0; i < M; ++i) { in >> a >> b; g[a-1].push_back(b-1); g[b-1].push_back(a-1); }
dfs(0); copy(ALL(cycle), ostream_iterator<int>(out, "\n")); }
OBS: daca l-as scrie din nou probabil n-as mai face translatarea range-ului de la 1..N la 0..N-1 si inapoi. Am facut-o doar pentru ca nu-mi place mie numaratul de la 1.
|
|
|
Memorat
|
|
|
|
•svalentin
|
|
« Răspunde #11 : Ianuarie 22, 2005, 10:57:13 » |
|
Eu "stergeam" muchiile marcandu-le cu -1... da, din cauza asta nu mi-a intrat in timp!
|
|
|
Memorat
|
|
|
|
|