Informatyka UJ forum

Spectro

[link widoczny dla zalogowanych]

Kolejne zadanie z prezadaniem :> .

mateo

[link widoczny dla zalogowanych]

Identyczne zadanko z OPSSa.
edit: a tak wogole to to zadanko jest 10te jesli chodzi o najmniejsza ilosc acceptow na OPSSie:)

Rogal

Kocham zadania w których wersja z STL-em dostaje OK z miejsca, a wersja bez niego oczywiście nie mieści się w czasie... :evil: No to zadanko sprwadza się do dobrego zaimplementowania operacji na grafie.

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

Ma ktoś jakąś zOKeyowaną binareczkę? Może być z STLem, ale nie musi ;)) Z góry dzięki.

kg86

mial ktos w tym zadaniu ANSa z "niewyjasnionych" przyczyn? :) bo ja wlasnie mam takowego i nie moge znalezc testu, na ktorym by mi sie program wywalal... moze ktos zarzuci jakims dobrym testem? :) generator testow cct'a nie chce mi dzialac, albo ja nie wiem jak go obslugiwac, natomiast w binarce zle czyta dane podane "z palca"...
btw. jak konstruujecie ten graf w tym zadaniu? :) bo chyba tylko w tym moge miec blad [zadnie V poszlo bez problemu]

chlebek

W zdaniu U to zmienialem tylko wczytywanie i wielkosc tablic, a reszta tak samo jak w V.

kg86

no ja tez tylko to zmienilem, i dlatego zastanawiam sie skad jest ANS, a jak wczytujesz dane? :)

hansu

Yyy, a jak Ty ten graf konstruujesz? Bo chyba nie robisz tego tak ze wczytujesz ten dany graf "na zywca" i po nim puszczasz przeplyw...

EDIT (bo przeczytalem Twoj post na TCSie ;)):

Skoro napisales cos o podwajaniu wierzcholkow to zakladam ze znasz idee algorytmu, czyli to ze podwajamy kazdy wierzcholek, do jednego z nowopowstalych synow podpinamy wszystkie krawedzie wchodzace, a do drugiego wychodzace, i laczymy te wierzcholki krawedzia o przepustowosci 1 (od tego z wchodzacymi, do tego z wychodzacymi i dzieki temu upewniamy sie ze kazda sciezka przechodzaca przez ten wierzcholek "pojdzie" ta wlasnie krawedzia miaedzy synami). Jesli tak wlasnie robisz (a zakladam ze robisz ;)) to jedyny blad jaki mi przychodzi na mysl to akcje dziejace sie przy zrodle i ujsciu. No bo tak naprawde wierzcholkow 1 i n nie podwajamy (albo podwajamy i nie podpinamy tam zadnych krawedzi, ale to juz szczegol implementacyjny dla leniwych programistow jak ja :P). Mozliwe wiec ze to przy tym masz blad jakis...

Gorfin

1
5 6
1 2
1 4
2 4
4 3
4 5
3 5

1

kg86

blad juz naprawiony, okazalo sie, ze zle przeczytalem tresc zadania :/ oczywiscie tworzyl graf "zgodnie z instrukcja", ale przeplywy reprezentujace odpowiednio krawedz "do" i krawedz "powrotna", byly ustawione na 1, 0... zamiast na 1, 1 :P bo polaczenie zachodzi w obu kierunkach, a nie jednym... tak samo krawedzie pomiedzy podwojonymi wierzcholkami...

exeman

Czy moglby ktos przyblizyc idee algorytmu? Z gory dzieki.

r4ku

idea jest taka, ze musimy odpowiednio zmodyfikowac otrzymany na wejsciu graf, tak zeby komputery byly reprezentowane przez krawedzie i wtedy puszczamy maksymalny przeplyw i jego wartosc jest rozwiazaniem.
wszystkie komputery poza ujsciem i zrodlem dublujemy - tworzymy nowe wierzcholki i podpinamy do nich krawedzie w ten sposob:
mamy krawedz nieskierowana pomiedzy komputerami a-b to podwajamy komputery a i b i tworzymy pomiedzy nimi polaczenie:
a->b(1) oznacza krawedz skierowana z a do b o przepustowosci 1
wiec dokladamy a' i b' i teraz mamy krawedzie:
a'->b(1)
b->a'(0)
b'->a(1)
a->b'(0)

oraz polonczenie pomiedzy a' i a, b' i b
a->a'(1)
a'->a(0)
b->b'(1)
b'->b(0)

w efekcie wszystkie krawedzie wchodzace do a maja przepustowosc 1 (poza a'->a) a wszystkie wychodzace 0 (poza a->a'), natomiast wszystkie wychodzace z a' maja 1 (poza a'->a) a wchodzace 0 (poza a->a')

komputerow 1 i N nie podwajamy i podpinamy do nich krawedzie analogicznie. kiedy mamy juz taki graf to puszczamy na min karpia i wypisujemy wynik

exeman

a przeplyw puszczamy miedzy 1, a n1 wierzcholkiem?

Skrobocik

Tak, tu mamy podane, że source jest "1", a target to "n" ;)

exeman

Mam troche inaczej, ale przeszlo. Podziekowania dla chlebka. :)

Skrobocik

Jeśli ktoś ma problem z RTE w tym zadaniu, to niech sprawdzi, czy jest przygotowany na taką sytuację, że w krawędzi jako pierwszy parametr podane jest ujście (czyli n), lub jako drugi - źródło (czyli 1), bo ja właśnie dlatego złapałem gwiazdkę :?
Dzięki Cecet za generatorek, bo mi właśnie takim testem zarzucił: