Informatyka UJ forum

r4ku

[link widoczny dla zalogowanych]

kg86

tym razem warto to zadanko przepchnac :)

chlebek

Mam prosbe do tych osob co juz przepchneli to zadanie. Mozna prosic o binarke ?

przem

Jak wyglada u was reprezentacja grafu w pamieci?

ok juz nieaktualne, jak by co to u mnie wyglada tak:

Spectro

Pierwsze zadanie z ASD, w którym zmuszony zostałem używać shortów :P . Dostałem RTE, bo początkowo wartości przepustowości i przepływu były intami. Cóż, tak to jest, jak się pisze na liście i używa się dużo razy operatora new ;] .

Stasiu

ja ponawiam prosbe, ktos moze zapodac binarke?

chlebek

[link widoczny dla zalogowanych]

Stasiu

dzieki :)

Pestka · pijak Dołączył: 22 Mar 2006 Posty: 79 Przeczytał: 0 tematów

kafex

Pierwszy strzal to to, że czegoś nie czyści :)

cheater_

A tak swoją drogą, to karp będzie do zaimplementowania w jakimś zadaniu obowiązkowym, czy tak piszecie bo jesteście zbokami?

Spectro

@Pestka:
Powinno być 23 12. Ja mam zazwyczaj bardzo ograniczone zaufanie do programów, które przechodzą przez Athinę ;] .

chlebek

Skrobocik

Macie może jeszcze jakieś testy, które potencjalnie mogłyby obnażyć ukryte błędy obliczeniowe mojego programu :?: , bo się ANS przyczłapał :/

neino

hej,

..a macie jakies szczegolnie szybciutkie te swoje BFS-y !?
bede wdzieczny za zerkniecie na ponizszy kod i jego ocene, gdyz wydaje mi sie, ze to przez niego wlasnie dostaje na zadanku Z2 TLE....

bool bfs () {
int u,v;
M[start]= infinity;
for (u=0; u<=n; u++) color[u] = WHITE;//(*)
head = tail = 0;
enqueue(start); //tail++;
pred[start] = -1;
while (head!=tail) {
u = dequeue();//head++;
for (int j=count2[u-1];j<count2[u];j++) {
int v = krawedz[j].dokad;
if (color[ v ]==WHITE && (krawedz[j].waga-krawedz[j].flow)>0) {
pred[ v ] = j;
M[v] = min(M[u], krawedz[j].waga-krawedz[j].flow);
if (v==target) return true;
enqueue(v);
}
}
}
return color[target]==BLACK;
} // actual_flow=M[target]

juz nawet linijke (*) zoptymalizowalem, zeby przy kazdorazowym wywolaniu BFS-a czyscil colory tylko na zmienionych wezlach, ale ciagle dziala zbyt dlugo...

pozdro !
Kamil