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 modificari inainte de aplicarea algoritmului. Trebuie adăugate încă două noduri (sursa si destinaţia fluxului) S şi D. Vom trage o muchie 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 negative, trebuie aplicat algoritmul Bellman-Ford, soluţia având astfel complexitate O(FLUX*N*M). O astfel de abordare obţine 50 de puncte. Pentru punctaj maxim, trebuie folosită o coadă la implementarea Bellman-Ford-ului. De observat că deşi teoretic aceşti algorimti se comportă destul de prost, în practica vor rula mult mai bine.
În cazul problemelor când cuplajul maxim va fi min(L,R), se recomanda folosirea Algoritmului lui Kuhn. Această abordare are complexitate O(N4), însă ca şi fluxul normal, se comportă mult mai bine în practică.
Aplicaţii
Infoarena - Adapost
