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 #include #include #include #include #include #define REP(i, n) for(int i = 0; i < n; i++) #define FWD(i, a, b) for(int i = a; i < b; i++) #define ALL(u) (u).begin(), (u).end() using namespace std; typedef pair PII; typedef long long LL; const int MAXN = 2010; struct edge { int u, v; LL w; bool operator<(edge x) const { return w < x.w; } }; class FindUnion { vector pre, height; public: FindUnion(int n) { pre.clear(); height.clear(); pre.resize(n); height.resize(n, 1); REP(i, n) pre[i] = i; } int find(int u) { if (u != pre.at(u)) pre[u] = find(pre.at(u)); return pre.at(u); } bool link(int u, int v) { u = find(u); v = find(v); if (u == v) return false; if (height[u] > height[v]) { swap(u, v); } pre[u] = v; if (height[u] == height[v]) { height[v]++; } return true; } }; int main() { int n; scanf("%d", &n); LL cost = 0; vector E; auto fu = FindUnion(n+1); REP(i, n) { FWD(j, i, n) { LL val; scanf("%lld", &val); E.push_back(edge({i, j+1, val})); } } sort(ALL(E)); for (edge e : E) { if (fu.link(e.u, e.v)) { cost += e.w; } } printf("%lld\n", cost); return 0; }