Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | cmcm.in, cmcm.out | Sursă | Arhiva Educationala |
Autor | Arhiva Educationala | Adăugată de | |
Timp execuţie pe test | 0.6 sec | Limită de memorie | 20480 kbytes |
Scorul tău | N/A | Dificultate | N/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 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 |
Explicaţie
...