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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <stdio.h>
#include <stdlib.h>

#define MX 2000000000;

// szanowne jury - nie mam pomyslu

int isOne(int *t, int a, int b) {
        int s,r;
        if (a>b) {
                s = a; a = b; b = s;
        }
        s = b-a;
        r = -1;
        for (;a<=b;a++) {
                if (t[a]) s--;
                else r = a;
        }
        return s==0 ? r : -1;
}

int main() {
        int n,i,j,a,c,k,l;
        int **g;
        int *next;
        int *view,*pv, *lv;
        int *weight;
        long long int s;

        scanf("%d", &n);
        g = malloc(n*sizeof(*g));
        next = malloc(n*sizeof(*next));
        view = malloc(n*sizeof(*view));
        pv = malloc(n*sizeof(*pv));
        lv = malloc(n*sizeof(*lv));
        weight = malloc(n*sizeof(*weight));
        for (i=0; i<n; ++i)
                g[i] = malloc(n*sizeof(**g));

        for (i=0; i<n; ++i) {
                for (j=i; j<n; ++j) {
                        scanf("%d", &a);
                        g[i][j] = g[j][i] = a;
                }
                weight[i] = g[i][i];
                pv[i] = i;
                lv[i] = i;
        }

        for (i=0; i<n; ++i) {
                next[i] = view[i] = 0;
        }

        for (j=0; j<n; ++j) {
//              printf("===================\n");
//              for (i=0;i<n;++i) printf("%d", view[i]);
//              printf("\n");
                for (k=0; k<n; ++k) {
                for (i=k; i<n; ++i) {
                        c = isOne(view, k, i);
                        if (c >= 0 && weight[c] > g[k][i]) {
                                weight[c] = g[k][i];
                                pv[c] = k;
                                lv[c] = i;
                        }
                }
                }

//              for (i=0; i<n; ++i) printf("%d - %d %d\n", weight[i], pv[i]+1, lv[i]+1);

                a = MX;
                for (i=0; i<n; ++i) {
                        if (!view[i] && weight[i] < a ) {
                                a = weight[i];
                                c = i;
                        }
                }

//              printf("%d %d\n", pv[c]+1, lv[c]+1);

                view[c] = 1;


        }
// */
        s = 0;
        for (i=0; i<n; ++i) {
//              printf("%d\n", weight[i]);
                s += weight[i];
        }

        printf("%Ld\n", s);
        return 0;

}