problema diagonala minima pe matrice

[•infoidiot]

Problema este urmatoarea:

"
Se citeste de la tastatura o matrice patratica a cu n linii * n coloane. Scrieti un program care, efectuand o succesiune de operatii de interschimbare a doua linii intre ele, sau a doua coloane intre ele, rearanjeaza liniile si coloanele matricii intr-o alta ordine, astfel incat suma elementelor de pe diagonala principala sa fie minima.
"

E posibil sa se rezolve cu programare dinamica dar nu am reusit sa-mi dau seama cum inca...

Mersi anticipat pt orice idee...

[•klamathix]

Faci un cuplaj maxim de cost minim pe matricea asta, apoi aranjezi liniile si coloanele astfel incat toate celulele selectate sa fie pe diagonala principala.