Informatyka UJ forum

Gorfin

@cct: albo mi sie wydaje, albo Twoje binarki do V nie chodza na przykladowym tescie :)

cct · pijak Dołączył: 21 Mar 2006 Posty: 202 Przeczytał: 0 tematów

Gorfin

O to "z palca" mi chodzilo :)

Dzieki za wszystkie materialy.

neino

...poniewaz mam reprezentacje grafu Robsona a mimo wszystko walcze obecnie z TLE w zadaniu V i nie wiem zbytnio co poprawic to przedstawie swoja idee :

moja funkcja max_flow() wyglada w skrocie tak :

while (bfs()) { //tu wlasciwie z reprezentacja taka jak opisal cct_
1.wyznacz wartosc sciezki powiekszajcej //=increment
2. while (pred[u]>=0) { //istnieje poprzednik w sciezce
int v=pred[u];
int kon=count[v];
int pocz=count[v-1];
for (int i=pocz;i<kon;i++) {
if (krawedz[i].skad==v && krawedz[i].dokad==u) krawedz[i].flow+=increment;
}
kon=count[u];
pocz=count[u-1];
for (int i=pocz;i<kon;i++) {
if (krawedz[i].skad==u && krawedz[i].dokad==v) krawedz[i].flow-=increment;
}
u=pred[u];
}
max_flow += increment;
}
return max_flow;

mam wrazenie, ze to poprawianie krawedzi (petle for) powinno sie odbywac szybciej..co wy ludzie stosujecie tutaj bin_search-a :] ??
ogolnie bede wdzieczny za jakies sugestie,

pozdrawiam,
Kamil 'neino'

Spectro

(trzecia wersja posta)

@neino:
Zmień BFSa na DFSa rekurencyjnego, jeżeli ta nazwa nie jest historyczna ;) .
A w DFSie zapamiętuj ścieżkę rozszerzającą w odpowiedniej tablicy. W tym zadaniu niestety liczy się stała ;] .

kg86

DFS w V jest bardzo istotny :) nie wnikalem bardzo dokladnie na czym polega graf Robsona - Ceceta :D ale zrobilem cos podobnego: rowniez posortowalem krawedzie leksykograficznie, a nastepnie kazdemu wierzcholkowi przyporzadkowalem 2 indeksy - pierwsza krawedz ktora z niego wychodzi i ostatnia :) takie przyporzadkowanie mozna zrobic liniowo po posortowaniu :) a wyznaczanie sciezki powiekszajacej robie w ten sposob, ze w struktrze wierzcholek ma zmienna "ktora", ktora oznacza indeks krawedzi ktora dotarlem do tego wierzcholka - potem wystarczy (po wyznaczeniu minimalnej krawedzi) isc od tylu i akutalizowac przeplywy :)
aha, i wydaje mi sie to istotne, aby kazdej krawedzi przyporzadkowac indeks krawedzi ktora idzie w druga strone - lepiej raz dla wszystkich, niz kilka razy dla tych samych, chociaz jeszcze lepiej jest wyznaczac to dynamicznie tylko wtedy kiedy trzeba, ale nie wiecej niz raz, dla danej krawedzi :) ja wyznaczalem raz dla wszystkich i TLE nie dostalem :)

chlebek

Faktem jest, ze DFS jest lepszy w tym zadaniu, ale mi V i U przeszlo mi BFS ;]

neino

Spectro

@neino:
Np. w każdej krawędzi trzymać indeks krawędzi przeciwnej. Tak, jak to opisał cct.

neino

hmm...dzieki za pomoc...ale wciaz TLE :]

obecnie polaczenia trzymam w tablicy

struct TKrawedz {
int skad,dokad,flow,waga;
int odwr;//indeks odwrotnej krawedzi,zmieniajacy sie jedynie przy qSORT
};

moze niepotrzebnie trzymam n1+n2 polaczen ze zrodla do wierzcholkow i z wierzcholkow do ujscia ? :/

EDIT : przeszlo :) po zmianie DFS-a na rekurencyjnego...dzieki cct za Twoja wersje ;] do wszystkich : nie warto uzywac tu kolejki do trzymania wierzcholkow DFS

exeman

exeman

Generator do V ma wszedzie napisane, ze jest generatorem do U, o co chodzi?

exeman

cct, wstawiles delaye w ten generator? Bo generowanie np. 100 malych testow to wiecznosc trzeba czekac, ja czekalem z 10 minut i przerwalem

cct · pijak Dołączył: 21 Mar 2006 Posty: 202 Przeczytał: 0 tematów

Rogal

cct: Użyj seta :wink:

exeman

A nawet bez kombinowania, to nie trzeba tej tablicy czyscic. Wystarczy wpisywac numer aktualnego zestawu.

cct · pijak Dołączył: 21 Mar 2006 Posty: 202 Przeczytał: 0 tematów

Nie chce mi się, są fajniejsze rzeczy do roboty niż babranie się z minionymi zadankami i niepotrzebne otwieranie edytora. ;)

(BTW@exeman: mi generowanie 100 testów z parametrami 100 zajęło parę sekund, widać Ci się zapętliło; na 1000 1000 1000 czekałem 3mmin na procku 1,5GHz).

cheater_

cct, czemu twoja binarka liczy test max do V (10MB) w 21sek, a moja w 4sek? :P ale pomijając to, przydała się, danke ;)

EDIT: żebyście przypadkiem nie pomyśleli że koduję o takiej porze :P skodowałem wcześniej, taraz się opierdalam :P

cct · pijak Dołączył: 21 Mar 2006 Posty: 202 Przeczytał: 0 tematów

Madras

Oh yeah, cały dzień spędzony na walce z TLE, całe szczęście to było, mam nadzieję, ostatnie zadanie z ASD w moim życiu ;].