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
// prim

int T,M,N,K,I,a,b,c,ans,cnt;
int dis[105][105];
bool mst[105];
priority_queue<pii> q;

void init(){
  memset(mst, 0, sizeof(mst));
  ans = 0;
  for(int i=0;i<N;i++)for(int j=0;j<N;j++)
    cin>>dis[i][j];
}
void sol(){
  int v,w;
  mst[0] = 1;
  for(int i=0;i<N;i++)if(dis[0][i])
    q.push(MP(-dis[0][i], i));
  while(!q.empty()){
    v = q.top().Y, w = -q.top().X;
    q.pop();
    if(mst[v]) continue;
    mst[v] = 1;
    ans += w;
    for(int i=0;i<N;i++)if(!mst[i] && dis[v][i])
      q.push(MP(-dis[v][i], i));
  }
  cout<<ans<<endl;
}

int main(){
  ios::sync_with_stdio(false);cin.tie(0);
  while(cin>>N){
    init();
    sol();
  }
}

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
// kruskal  

struct Node{
  int f, t, l;
  Node(int F=0, int T=0, int L=0):
    f(F), t(T), l(L){}
  bool operator < (const Node& a)const{
    return l<a.l;
  }
}e[10005];
int T,M,N,K,I,a,b,c,ans,cnt;
int par[105];

void init(){
  cnt = ans = 0;
  for(int i=0;i<N;i++) par[i] = i;
  for(int i=0;i<N;i++)for(int j=0;j<N;j++){
    cin >> a;
    e[cnt++] = Node(i,j,a);
  }
}
int _find(int v){
  return (par[v] == v ? v : par[v] = _find(par[v]));
}
void sol(){
  int t1,t2;
  Node t;
  sort(e, e+cnt);
  for(int i=0;i<cnt;i++){
    t = e[i];
    t1 = _find(t.f), t2 = _find(t.t);
    if(t1 == t2) continue;
    (i&1) ? par[t1]=t2 : par[t2]=t1;
    ans += t.l;
  }
  cout<<ans<<endl;
}

int main(){
  ios::sync_with_stdio(false);cin.tie(0);
  while(cin>>N){
    init();
    sol();
  }
}