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
#include <iostream>
#include <algorithm>
#include <list>
using namespace std;

#define MAXN 2000

pair<int, pair<int, int> > ranges[MAXN * MAXN / 2];

bool taken[MAXN+1][MAXN+1];


list<list<int> > elem;

void add(int i, int j) {
    list<list<int> >::iterator iti = elem.begin(), itj = elem.begin();
    list<int>::iterator iti2, itj2;
    while(iti != elem.end()) {
        for(iti2 = (*iti).begin(); iti2 != (*iti).end() && *iti2 != i; iti2++);
        if(iti2 != (*iti).end())
            break;
        else
            iti++;
    }

    while(itj != elem.end()) {
        for(itj2 = (*itj).begin(); itj2 != (*itj).end() && *itj2 != j; itj2++);
        if(itj2 != (*itj).end())
            break;
        else
            itj++;
    }

    if(iti == elem.end() && itj == elem.end()) {
        list<int> l;
        l.push_back(i);
        l.push_back(j);
        elem.push_back(l);
        taken[i][j] = true;
    }
    else if(iti != elem.end() && itj == elem.end()) {
        (*iti).push_back(j);
        for(list<int>::iterator it = (*iti).begin(); it != (*iti).end(); it++) {
            taken[*it][j] = true;
            taken[j][*it] = true;
        }
    }
    else if(iti == elem.end() && itj != elem.end()) {
        (*itj).push_back(i);
        for(list<int>::iterator it = (*itj).begin(); it != (*itj).end(); it++) {
            taken[*it][i] = true;
            taken[i][*it] = true;
        }
    }
    else if(iti != elem.end() && itj != elem.end()) {

        for(list<int>::iterator it = (*iti).begin(); it != (*iti).end(); it++) {
            for(list<int>::iterator jt = (*itj).begin(); jt != (*itj).end(); jt++) {
            taken[*it][*jt] = true;
            taken[*jt][*it] = true;
            }
        }

        (*iti).splice((*iti).begin(),*itj);
        elem.erase(itj);
    }
}


int main()
{
    int n, m = 0;
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = i; j < n; j++) {
            cin >> ranges[m].first;
            ranges[m].second.first = i;
            ranges[m].second.second = j;
            m++;
        }

    sort(ranges, ranges + m);

    int k = n;
    long long total = 0;
    m = 0;
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= n; j++)
            taken[i][j] = false;


    while(k > 0) {
        if(!taken[ranges[m].second.first][ranges[m].second.second+1]) {
            add(ranges[m].second.first, ranges[m].second.second+1);
            total += ranges[m].first;
            k--;
        }
        m++;

    }


    cout << total << endl;
    return 0;
}