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
124
/*************************************************************************
 *   Zadanie:           Kuglarz                                          *
 *   Zlozonosc czasowa: O(n^2 log n)                                     *
 *   Wynik:             --/10                                            *
 *************************************************************************/

#include <iostream>
#include <vector>
#include <algorithm>

#define FOR(i,b,e) for(int i=(b); i <= (e); ++i)
#define SIZE(c) (int) (c).size()
#define FOREACH(i,c) FOR(i,0,SIZE(c)-1)
#define PB push_back

using namespace std;

struct FAU
{
    vector < int > p; //parent
    vector < int > r; //rank
    int cnt;

    FAU(int n)
    {
        p.resize(n,-1);
        r.resize(n,0);
        cnt = n;
    }

    int Find(int x)
    {
        if (p[x] == -1) return x;

        p[x] = Find(p[x]);
        return p[x];
    }

    bool Connected(int x, int y)
    {
        return (Find(x) == Find(y));
    }

    void Union(int x, int y)
    {
        x = Find(x);
        y = Find(y);

        if (x == y) return ;

        --cnt;

        if (r[x] > r[y]) p[y] = x;
        else p[x] = y;

        if (r[x] == r[y]) ++r[y];

        return ;
    }

    int HowMany(void)
    {
        return cnt;
    }
};

struct edge
{
    int u;
    int v;

    int d;

    edge(int nu, int nv, int nd)
        { u = nu; v = nv; d = nd; }
};

bool comp(edge a, edge b)
{
    return (a.d < b.d);
}

/*************************************************************************/

int main()
{
    ios_base::sync_with_stdio(0);

    int n;
    cin >> n;

    FAU F(n+1);
    vector < edge > E;

    FOR(i,0,n-1) FOR(j,i+1,n)
    {
        int t;
        cin >> t;

        E.PB( edge(i,j,t) );
    }

    sort(E.begin(), E.end(), comp);

    long long int cost = 0;
    FOREACH(i,E)
    {
        int u = E[i].u, v = E[i].v;

        if (!F.Connected(u,v))
        {
            cost += E[i].d;
            F.Union(u,v);
        }

        if (F.HowMany() == 1) break;
    }

    cout << cost;

    return 0;
}

/*************************************************************************/