文件目录

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int f[105][105];
bool vis[105];
int fat[105];
int n, x, y, w, ans = 0;
struct node
{
    int to, w;
    bool operator<(const node &b) const
    {
        return w > b.w;
    }
};
void prim()
{
    priority_queue<node> p;
    p.push({1, 0});
    while (!p.empty())
    {
        node u = p.top();
        p.pop();
        if (vis[u.to])
            continue;
        vis[u.to] = true;
        if (fat[u.to] != u.to)
            ans += f[fat[u.to]][u.to];
        for (int i = 1; i <= n; i++)
        {
            if (!vis[i] && f[u.to][i] < f[0][0])
            {
                p.push({i, f[u.to][i]});
                if (f[u.to][i] < f[fat[i]][i])
                    fat[i] = u.to;
            }
        }
    }
}
int main()
{
    memset(f, 0x3f, sizeof(f));
    cin >> n;
    for (int i = 1; i <= n; i++)
        fat[i] = i;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> f[i][j];
            if (i == j)
                f[i][j] = f[0][0];
        }
    }
    prim();
    cout << ans;
    return 0;
}