#include <iostream>
using namespace std;
const int MAXVAL = 10000;
int
gra[1001][1001] = {MAXVAL}, n, mp = 0, ans = 0; //prim[to][weight]
struct papp
{
int
to, wei;
papp()
{
to = wei = 0;
}
}p[1001];
void
__read__()
{
cin >> n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
cin >> gra[i][j];
for(int i = 1; i <= n - 1; i++)
{
p[i].to = i + 1;
p[i].wei = MAXVAL;
}
p[0].to = 1;
}
void
swap(papp &x, papp &y)
{
papp t = x;
x = y;
y = t;
}
int
findmin(int i)
{
int m = MAXVAL;
for(int j = i; j <= n - 1; j++)
if(p[j].wei < m)
{
m = p[j].wei;
mp = j;
}
return m;
}
void
__prim__(int en)
{
if(en < n - 1)
{
for(int i = en + 1; i <= n - 1; i++)
if(gra[p[en].to][p[i].to] < p[i].wei
&& gra[p[en].to][p[i].to] > 0)
p[i].wei = gra[p[en].to][p[i].to];
//update the table
findmin(en + 1);
if(mp)
swap(p[mp], p[en + 1]);
ans += p[en + 1].wei;
__prim__(en + 1);
}
}
int
main()
{
__read__();
__prim__(0);
cout << ans << endl;
return 0;
}
|