Cerinţa

Se dă o matrice pătratică cu n lini şi n coloane şi elemente numere naturale distincte. Determinaţi cea mai mare sumă a n elemente din matrice, cu proprietatea că oricare două elemente se află pe linii şi coloane distincte.

Date de intrare

Fişierul de intrare summax.in conţine pe prima linie numărul n, iar pe următoarele n linii câte n numere naturale, separate prin spaţii, reprezentând elementele matricei.

Date de ieşire

Fişierul de ieşire summax.out va conţine pe prima linie numărul S, reprezentând suma maximă determinată.

Restricţii şi precizări

• 1 ≤ n ≤ 10
• elementele matricei vor avea cel mult 4 cifre

Exemplu

summax.in

4
12 16 5 4
11 14 6 7
8 2 3 17
10 9 13 15

summax.out

57

Explicație

57=16+11+17+13.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("summax.in");
ofstream cout("summax.out");

int x[11] , p[11] , a[11][11] , n , smax , s;


void back(int k)
{
    for(int i = 1 ; i <= n ; ++i)
        if(!p[i])
        {
            p[i] = 1;
            x[k] = i;
            if(k == n)
            {
                s = 0;
                for(int j = 1 ; j <= n ; j++)
                    s += a[j][x[j]];
                if(s>smax) smax = s;
            }
            else back(k + 1);
            p[i] = 0;
        }
}
int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= n ; ++j)
            cin >> a[i][j];
    back(1);
    cout << smax;
    return 0;
}