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ă oricărui nod v din V îi va corespunde cel mult o muchie din mulţimea M. 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. Pe fiecare din următoarele Nr linii se va găsi un număr x, indicând indicele unei muchii folosite pentru construcţia cuplajului soluţie.
Restricţii
- 1 ≤ N, M ≤ 300
- 1 ≤ E ≤ 20 000
- -50 000 ≤ C ≤ 50 000
- Valorie x se vor afişa în ordine crescătoare
- În caz că există mai multe soluţii puteţi afişa oricare
Exemplu
| cmcm.in | cmcm.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
