Fişierul intrare/ieşire:cmcm.in, cmcm.outSursăArhiva Educationala
AutorArhiva EducationalaAdăugată desavimSerban Andrei Stan savim
Timp execuţie pe test1.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cuplaj maxim de cost minim

Se dă un graf neorientat bipartit G(V=(L,R),E) cu costuri pe muchii. Definim un cuplaj în graf ca fiind o submulţime de muchii M ⊂ E, cu prorietatea că pentru orice nod v din V, va exista cel mult o muchie în mulţimea M incidentă în v. Costul unui cuplaj este determinat de suma costurilor muchiilor care îl compun.

Cerinţă

Pentru un graf G, să se determine cuplajul de cardinal maxim şi cost minim.

Date de intrare

Pe prima linie a fişierului de intrare cmcm.in se vor găsi trei numere N, M şi E, reprezentând cardinalul mulţimii L, cardinalul mulţimii R, respectiv numărul de muchii din graf. Pe următoarele E linii se vor găsi câte trei numere naturale P, Q şi C, cu semnificaţia că există o muchie de la nodul P din L la nodul Q din R de cost C.

Date de ieşire

Pe prima linie a fişierului de ieşire cmcm.out veţi afişa două numere Nr şi K, reprezentând numărul de muchii din cuplajul maxim, precum şi costul minim al acestui cuplaj. A doua linie va conţine Nr numere reprezentând indicii muchiilor folosite pentru construcţia cuplajului soluţie.

Restricţii

  • 1 ≤ N, M ≤ 300
  • 1 ≤ E ≤ 50 000
  • -20 000 ≤ C ≤ 20 000
  • Indicii muchiilor se pot afişa în orice ordine.
  • În caz că există mai multe soluţii o puteţi afişa pe oricare.

Exemplu

cmcm.incmcm.out
6 10 12
5 3 5
4 7 -5
5 9 -1
1 2 -1
2 9 5
6 1 0
6 4 -5
3 9 3
4 10 -3
3 8 4
4 8 -5
5 2 6
6 3
4 5 10 2 1 7

Indicaţii de rezolvare

Această problemă este o aplicaţie la problema mai generală a fluxului maxim de cost minim, aici graful trebuind să suporte anumite modificări înainte de aplicarea algoritmului. Trebuie adăugate încă două noduri (sursa şi destinaţia fluxului) s şi d. Vom adăuga muchii de la s la fiecare nod din L de cost 0 şi capacitate 1, precum şi de la fiecare nod din R către d, tot de cost 0 si capacitate 1. Soluţia problemei va fi reprezentată de fluxul maxim de cost minim din această reţea. Datorită existenţei muchiilor de cost negativ, trebuie aplicat algoritmul Bellman-Ford, soluţie ce are ordinul de execuţie O(FLUX*N*M), cu FLUX reprezentând cardinalul cuplajului maxim. O astfel de abordare obţine 50 de puncte. O sursă pe această idee se poate găsi aici. Pentru punctaj maxim, trebuie implementat algoritmul Bellman-Ford cu coadă (o sursă doar a acestui algoritm se găseşti aici). Această implementare se poate găsi aici. De observat că deşi teoretic aceşti algoritmi necesită un timp mare de execuţie, în practică se comportă mult mai bine.

În cazul problemelor când cuplajul maxim va fi min(L,R), se recomandă folosirea Algoritmului lui Kuhn (Ungar). Puteţi citi despre acest algoritm pe infoarena şi pe wikipedia. Această abordare are complexitate O(N4), însă ca şi fluxul normal, se comportă mult mai bine în practică.

Dacă graful G are toate muchiile de cost egal, atunci problema se reduce la cuplajul maxim în graf bipartit.

Aplicaţii

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content