1094 Sabotaj

[•wefgef]

Aici puteti discuta despre problema Sabotaj.

[•APOCALYPTO]

Stiu sa aflu valoarea taieturii minime.
Imi poate spune cineva cum aflu muchiile?

[•pauldb]

Dupa ce ai facut flux, in graful rezidual vor exista niste muchii pentru care fluxul este egal cu capacitatea. Daca elimini acest muchii, graful tau devine neconex, deci inseamna ca taietura este inclusa in aceasta multime de muchii.

Poti face o parcurgere a grafului din sursa (sau destinatie) si sa treci doar prin muchii a caror flux este strict mai mic decat capacitatea. O posibila taietura minima este reprezentata de setul de muchii maximal ales astfel incat pentru fiecare muchie un nod sa fi fost vizitat in parcurgere si celalalt nod nu. Justificatia este destul de evidenta. Daca nu te descurci, mai intreaba.

[•APOCALYPTO]

Dupa ce ai facut flux, in graful rezidual vor exista niste muchii pentru care fluxul este egal cu capacitatea. Daca elimini acest muchii, graful tau devine neconex, deci inseamna ca taietura este inclusa in aceasta multime de muchii.

Pai eu le-am considerat pe toate muchiile care au fluxul egal cu capacitatea.
Adica, sa inteleg ca raspunsul nu este multimea muchiilor cu flux[ i ][ j ]=cap[ i ][ j ] , ci o submultime a acestei multimi?
Daca da, cum o determin(daca se poate fara parcurgere)?

[•pauldb]

Da, este o submultime. Exista niste cazuri destul de evidente pe care nu le tratezi, numarand doar muchiile pentru care capacitatea este egala cu fluxul. Sa consideram graful rezidual:

Cod:

N = 10, M = 13, sursa = 1, destinatie = 10
x, y, capacitate, flux
1 3 20 10
1 2 10 10
2 4 5 5
2 5 8 5 
5 4 20 5
4 3 20 10
3 6 20 20
6 10 5 5
6 7 15 15
7 8 10 10
8 9 10 10
7 9 5 5
9 10 15 15

Aici taieturi minime posibile sunt: {3 6}, {6 10, 9 10}, etc. Tu consideri mult prea multe muchii in taietura.

Eu nu cunosc vreo modalitate mai simpla (si corecta) cu care sa determini taietura, decat folosind o parcurgere.

[•APOCALYPTO]

Ok.
Multimesc mult pentru explicatia muncita .

[•lucian666]

  Salut

La problema aceasta iau 30 de pct cu 7 incorect si nu stiu de ce
Procedez astfel:
1.Aflux fluxul maxim al retelei de calculatoare
2.Aflux muchiile critice din retea ,acestea reprezentand solutia.

Pe exemplu imi merge  ,insa pe acesta:

Cod:

10 13
1 3 20
1 2 10
2 4 5
2 5 8 
5 4 20
4 3 20
3 6 20
6 10 5
6 7 15
7 8 10
8 9 10
7 9 5
9 10 15

imi afiseaza 20 0 ,desi corect ar trebui sa-mi afiseze 20 3
7
8
13 

Vreo sugesti ceva?
Multumesc Anticipat!!!

[•wefgef]

Ai citit posturile de mai sus?

[•AlexandruValeanu]

Salut!
Am calculat fluxul folosind Ford-Fulkerson si dupa aia am facut o parcurgere din sursa trecand doar prin muchii ce au capacitatea mai mare ca fluxul. In final, afisez toate muchiile ce au un capat viziat si unul nevizitat. Iau 30p cu WA. Imi poate spune cineva daca ideea de rezolvare este corecta? Multumesc anticipat!
sursa: http://www.infoarena.ro/job_detail/993364

[•a_h1926]

Salut!

Ideea de rezolvare e buna, dar problema iti cere sa calculezi costul minim astfel incat sa separi doua noduri din graf, iar tu calculezi costul ca sa separi nodurile 1 si N.
Pe exemplul:

Cod:

4 4
1 2 1
1 3 1
1 4 1
3 4 1

raspunsul este:

Cod:

1 1
2

Succes!

[•AlexandruValeanu]

Mersi de raspuns. Am inteles de ce greseam. As mai avea totusi o intrebare cum alegi sursa si dentinatia astfel incat taietura sa fie minima? Eu am incercat sa aflu taietura pentru orice pereche (i,j) cu i<j si ia 40p cu TLE. Am mai incercat sa fixed i(l-am luat pe i=1) si sa fac taietura pentru fiecara j, 1<=J<=n si nu ia mai mult de 60p. Am luat insa 90p cu 1 TLE mergand cu j doar de la N/2->N ceea ce nu este nici pe departe corect.

[•a_h1926]

Ideea e ca vrei sa stergi cateva muchii astfel incat graful sa se sparga in cel putin doua componente conexe. E clar ca nodul 1 va face parte din una din componentele conexe, astfel e suficient daca vei considera taieturile dintre perechi de noduri de forma (1, x) cu 2 <= x <= N. In sursa aceasta pe care iei 60 consideri doar taieturile de forma (1, x) cu x vecin al nodului 1, si de aceea nu e corect.

[•AlexandruValeanu]

Am facut asa cum mi-ai spus si am aflat taietura pentru ( 1, i ) cu 2 <= i <= N si sursa ia 70 cu 3 TLE.
Sursa: http://www.infoarena.ro/job_detail/993424

[•a_h1926]

Nu ai facut optimizarea fluxului cum trebuie. La linia 98, adauga:

Cod:

tata[D] = son;

De asemenea, cand faci parcurgerea BFS, in cazul in care nodul curent este destinatia, nu-l mai expanda (altfel ai putea gasi drum de la sursa la un nod x prin destinatie si cand fixezi tatal destinatiei poti intra intr-un ciclu infinit).

[•AlexandruValeanu]

Mersi foarte mult pentru toate raspunsurile. Am reusit sa fac problema intr-un final. Da cred ca aveai dreptate si la testele alea intra in ciclu infinit de la BFS. Multumesc inca o data!