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
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;

struct przedz
{
    int p, k, w;

    friend bool operator < (przedz a, przedz b)
    {
        return a.w< b.w;
    }
};

set<int> przod[2005], tyl[2005];
przedz tab[3000000];

void obacz (int p, int k)
{
    int y;
    przod[p].insert(k);
    tyl[k].insert(p);

    for (set<int>::iterator it=przod[p].begin(); it!=przod[p].end(); it++)
    {
        y=*it;

        if (y<k && przod[y+1].find(k)==przod[y+1].end())
        {
            przod[y+1].insert(k);
            tyl[k].insert(y+1);
            obacz(y+1,k);
        }

        if (y>k && przod[k+1].find(y)==przod[k+1].end())
        {
            przod[k+1].insert(y);
            tyl[y].insert(k+1);
            obacz(k+1,y);
        }
    }

    for (set<int>::iterator it=przod[k+1].begin(); it!=przod[k+1].end(); it++)
    {
        y=*it;

        if (przod[p].find(y)==przod[p].end())
        {
            przod[p].insert(y);
            tyl[y].insert(p);
            obacz(p,y);
        }
    }

    if (p)
    for (set<int>::iterator it=tyl[p-1].begin(); it!=tyl[p-1].end(); it++)
    {
        y=*it;

        if (przod[y].find(k)==przod[y].end())
        {
            przod[y].insert(k);
            tyl[k].insert(y);
            obacz(y,k);
        }
    }

    for (set<int>::iterator it=tyl[k].begin(); it!=tyl[k].end(); it++)
    {
        y=*it;

        if (y<p && przod[y].find(p-1)==przod[y].end())
        {
            przod[y].insert(p-1);
            tyl[p-1].insert(y);
            obacz(y,p-1);
        }

        if (y>p && przod[p].find(y-1)==przod[p].end())
        {
            przod[p].insert(y-1);
            tyl[y-1].insert(p);
            obacz(p,y-1);
        }
    }
}

int main ()
{
    int n,a,b,mam=0,nabite=0;
    long long w=0;
    przedz kaka;

    scanf ("%d", &n);

    for (a=0; a<n; a++)
        for (b=a; b<n; b++)
        {
            kaka.p=a;
            kaka.k=b;
            scanf ("%d", &kaka.w);
            tab[mam++]=kaka;
        }

    sort(tab, tab+mam);

    for (a=0; nabite<n; a++)
    {
        kaka=tab[a];

        if (przod[kaka.p].find(kaka.k)==przod[kaka.p].end())
        {
            nabite++;
            w+=(long long)kaka.w;
            obacz(kaka.p, kaka.k);
        }
    }

    printf ("%lld", w);

    return 0;
}