Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | cmcm.in, cmcm.out | Sursă | Arhiva Educationala |
| Autor | Arhiva Educationala | Adăugată de |  Serban Andrei Stan •savim |
| Timp execuţie pe test | 0.6 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.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 in 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ă in 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 si 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 muţimii L, cardinalul mulţimii R, respectiv numărul de muchii din graf. Pe următoarele E linii se vor găsi cate trei numere naturale P,Q si C, cu semnificaţia ca 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 veti afişa două numere Nr si K, reprezentând numărul de muchii din cuplajul maxim, precum si 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 puteţi afişa oricare
Exemplu
| cmcm.in | cmcm.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 fluxul maxim de cost minim, graful trebuind să suporte anumite modificări înainte de aplicarea algoritmului. Trebuie adăugate încă două noduri (sursa si destinaţia fluxului) S şi D. Vom trage 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ţia având astfel complexitate O(FLUX*N*M). O astfel de abordare obţine 50 de puncte. O sursă pe această idee se poate găsi aici. Pentru punctaj maxim, trebuie folosită o coadă la implementarea Bellman-Ford-ului. Această implementare se poate găsi aici. De observat că deşi teoretic aceşti algorimti necesită un timp mare de execuţie, în practica 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 aici şi aici. Această abordare are complexitate O(N4), însă ca şi fluxul normal, se comportă mult mai bine în practică.
Aplicaţii
Infoarena - Adapost
Infoarena - Traseu
Infoarena - Trafic
Infoarena - Cc
SGU - 252
