文件目录

// kruskal 贪心思想 并查集
#include <bits/stdc++.h>
using namespace std;
// 将所有边按照权重从小到大排序
// 遍历所有边，如果两点可以合并，进入mst(最小生成树)集
int n, m, t = 0, ans = 0;
struct edge
{
    int u, v, w;
    bool operator<(const edge &b) const
    {
        return w < b.w;
    }
} e[10050];
int fat[105];
void init()
{
    for (int i = 0; i < 105; i++)
        fat[i] = i;
}
int findfat(int x)
{
    if (fat[x] != x)
        fat[x] = findfat(fat[x]); // 路径压缩
    return fat[x];
}
void uset(int a, int b)
{
    int fa = findfat(a);
    int fb = findfat(b);
    if (fa != fb)
        fat[fb] = fa;
}
void kruskal()
{
    sort(e, e + t);
    int nn = 0;
    for (int i = 0; i < t; i++)
    {
        int u = e[i].u, v = e[i].v;
        if (findfat(u) != findfat(v))
        {
            uset(u, v);
            ans += e[i].w;
            // cout<<e[i].w<<" ";
            nn++;
        }
        if (nn + 1 == n)
            break;
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> m;
            if (m)
            {
                e[t].u = i;
                e[t].v = j;
                e[t].w = m;
                t++;
            }
        }
    }
    init();
    kruskal();
    cout << ans;
    return 0;
}