|
Titlul: 373 Paznici Scris de: Adrian Vladu din Martie 21, 2007, 22:37:08 Aici puteţi discuta despre problema Paznici (http://infoarena.ro/problema/paznici).
Titlul: Răspuns: 373 Paznici Scris de: Aurelian Namascu din Decembrie 23, 2010, 11:03:14 Salut!
Eu construiesc un graf bipartit si cu nodurile din stanga-etichetele liniilor si coloanelor, iar in drepta- elementele matricei, si pun legatura de la fiecare coloana la elementele de pe ea si de la fiecare linie la elementele de pe ea. Apoi aplic un algoritm cu complexitatea O(sqrt(V)*E) pentru ca *** este acelasi lucru cu *** si nu obtin ceea ce trebuie. Banuiesc ca nu creez graful bine. Imi spune cineva cum sa-l contruiesc corect? [Edit] Eu am pus 1-A 2-B .... 26-Z 27-a 28-b ... 52-z Si cand caut solutia pur si simplu ciclez printre noduri si verifica daca l-am imperecheat cu vreun nod din dreapta si dacada il imperechez . Mie pe exemplu imi da Cod: 10 Titlul: Răspuns: 373 Paznici Scris de: Paul-Dan Baltescu din Decembrie 23, 2010, 14:32:29 Da, nu construiesti graful bine. In stanga trebuie sa ai liniile, iar in dreapta coloanele. De la o linie la o coloana se trage o muchie daca celula determinata de linia si coloana respectiva este 1. Ca sa intelegi de ce se face constructia grafului astfel, poate te-ar ajuta sa citesti despre minimum vertex cover in grafuri bipartite si despre teorema lui Konig.
Titlul: Răspuns: 373 Paznici Scris de: Vlad Eugen Dornescu din Februarie 14, 2011, 13:30:18 Eu aflu suportul minim dupa ce fac un cuplaj maxim in graful bipartit (linie -> coloana).
1.Iau doar 80 de puncte cu WA, care ar putea fi problema? 2.Solutia trebuie sa fie minim lexicografica.Cuplajul maxim (cu lanturi alternante, garanteaza o solutie minim lexicografica pentru cuplaj - asa am dedus eu).Suportul unui graf bipartit nu e tot timpul o solutie unica. Cum pot sa aflu suportul de ordin minim lexicografic? Eu am c * 2 noduri care sunt cuplate in graf. Eu cand fac suport am : For(1 <= i <= catelinii am) calculeaza suport(i) daca nodul i nu e in cuplaj. Titlul: Răspuns: 373 Paznici Scris de: Vasilut Lucian din August 02, 2012, 11:11:30 Pt exemplul din enunt cuplajul este:
2 3 5 5 7 9 10 12 Cum pot sa-mi dau seama daca cand e litera mica si cand e litera mare? :-k Multumesc Anticipat!!! Titlul: Răspuns: 373 Paznici Scris de: Vasilut Lucian din August 04, 2012, 18:12:29 Pt exemplul din enunt cuplajul este: 2 3 5 5 7 9 10 12 Cum pot sa-mi dau seama daca cand e litera mica si cand e litera mare? :-k Multumesc Anticipat!!! Am calculat gradele fiecarui vf si dupa ce fac cuplajul afisez litera corespunzatoare vf din cuplaj care are gradul cel mai mare :'( iau doar 4 pct... Titlul: Răspuns: 373 Paznici Scris de: Vasilut Lucian din Septembrie 05, 2012, 08:22:28 Ma puteti ajuta cu un sfat? :)
Construiesc un graf (pun muchia ( i ,j ) daca a[ i][j]=1 ) Calculez gradele fiecarui vf din graful construit Fac apoi cuplajul ,apoi afisez litera coresp vf din cuplaj care are gradul cel mai mare.... ce e gresit in judecata mea? Multumesc Anticipat!!!! :) Titlul: Răspuns: 373 Paznici Scris de: Andrei Grigorean din Septembrie 05, 2012, 12:50:06 Cum îți garantează algoritmul tău găsirea unui cuplaj minim lexicografic?
Titlul: Răspuns: 373 Paznici Scris de: Vasilut Lucian din Septembrie 05, 2012, 18:37:12 Din cate stiu Cuplajul maxim cel cu lanturi alternante este minim din punct de vedere lexicografic :-k
Titlul: Răspuns: 373 Paznici Scris de: Vasilut Lucian din Octombrie 17, 2012, 19:05:38 Problema asta ma cam supara :-'. Imi construiesc un graf orientat G unde pun perechile (i,j) daca in matricea initiala a[ i ][j] =1.
Fac cuplaj maxim pe graful G si apoi pt fiecare pereche din cuplajul gasit(i,dr[ i ] ) verific care acopera o zona mai mare. Daca i acopera atunci afisez litera mare corespunzatoare,daca nu afisez litera mica. Pe exemplu merge ](*,) Vreo sugestie ceva? Multumesc Anticipat!!! :) |