373 Paznici

[•azotlichid]

Aici puteţi discuta despre problema Paznici.

[•gorgovan]

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
BEGJMcegil

[•pauldb]

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.

[•dornescuvlad]

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.
 

[•lucian666]

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?
Multumesc Anticipat!!!

[•lucian666]

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?
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...

[•lucian666]

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!!!!

[•wefgef]

Cum îți garantează algoritmul tău găsirea unui cuplaj minim lexicografic?

[•lucian666]

Din cate stiu Cuplajul maxim cel cu lanturi alternante este minim din punct de vedere lexicografic

[•lucian666]

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!!!