1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <stdio.h>
using namespace std;

int main(int argc, char** argv) {
    int ileKubkow;
    scanf("%d",&ileKubkow);
    int *ceny = new int[ileKubkow*ileKubkow];
    int *delty = new int[ileKubkow*ileKubkow];
    bool *zajete = new bool[ileKubkow*ileKubkow];
    int *indeksy = new int[ileKubkow];
    bool *zmieniony = new bool[ileKubkow];
    long long suma = 0;
    
    for(int odKubka=0; odKubka<ileKubkow; odKubka++){
        zmieniony[odKubka] = false;
        for(int doKubka=odKubka; doKubka<ileKubkow; doKubka++){
            scanf("%d",&(ceny[odKubka*ileKubkow + doKubka]));
            zajete[odKubka*ileKubkow + doKubka]=false;
        }
        indeksy[odKubka] = odKubka*ileKubkow + odKubka;
        zajete[indeksy[odKubka]]=true;
        suma += ceny[indeksy[odKubka]];
        zajete[indeksy[odKubka]]=true;
        for(int naZakresKubek=0; naZakresKubek<odKubka; naZakresKubek++){
            delty[odKubka*ileKubkow + naZakresKubek] = ceny[naZakresKubek*ileKubkow + odKubka] - ceny[indeksy[odKubka]];
        }
        for(int naZakresKubek=odKubka; naZakresKubek<ileKubkow; naZakresKubek++){
            delty[odKubka*ileKubkow + naZakresKubek] = ceny[odKubka*ileKubkow + naZakresKubek] - ceny[indeksy[odKubka]];
        }
    } 
    
    bool znalezionoLepsze = true;
    while(znalezionoLepsze){
        znalezionoLepsze = false;
        //szukanie najlepszej delty
        int min = 0;
        int kubek = 0;
        int indeksZ = indeksy[0];
        int indeksNa = indeksy[0];
        for(int zKubka=0; zKubka<ileKubkow; zKubka++){
            if(!zmieniony[zKubka]){ 
                for(int naZakresKubek=0; naZakresKubek<ileKubkow; naZakresKubek++){
                    int indeksPary;
                    if (zKubka>naZakresKubek) indeksPary = naZakresKubek*ileKubkow + zKubka;
                    else indeksPary = zKubka*ileKubkow + naZakresKubek;
                    if(!(zajete[indeksPary])){
                        if(delty[zKubka*ileKubkow + naZakresKubek]<min){
                            min = delty[zKubka*ileKubkow + naZakresKubek];
                            znalezionoLepsze = true;
                            kubek = zKubka;
                            indeksZ = indeksy[zKubka];
                            indeksNa = indeksPary;
                        }
                    }
                }
            }
        }
        //jeśli znaleziono wlasciwa Delte, to aktualizacja indeksu 
        if(znalezionoLepsze){
            suma += min;
            zajete[indeksZ] = false;
            zajete[indeksNa] = true;
            indeksy[kubek] = indeksNa;
            zmieniony[kubek] = true;
        }   
    }
    
    printf("%lld\n",suma);
    
    delete [] ceny;
    delete [] delty;
    delete [] zajete;
    delete [] indeksy;
    delete [] zmieniony;
    
    return 0;
}