# Untitled

unknown
plain_text
a year ago
1.2 kB
2
Indexable
Never
```#include<iostream>
using namespace std;
int n;
int a[105][105];

int prims(){

int u,v,min_distance,distance[105],from[105];
int visited[105],no_of_edges,i,min_cost,j;

//Khoi tao visited[],distance[] and from[]
distance[0]=0;
visited[0]=1;
for(i=1;i<n;i++)
{
distance[i]=a[0][i];
from[i]=0;
visited[i]=0;
}
min_cost=0; //Giá tri cua cây khung
no_of_edges=n-1; //So canh duoc thêm vào.
while(no_of_edges>0)
{
//Tìm dinh có khoang cách nho nhat den cây
min_distance=1000000;
for(i=1;i<n;i++){
if(visited[i]==0&&distance[i]<min_distance)
{
v=i;
min_distance=distance[i];
}
}
u=from[v];

no_of_edges--;
visited[v]=1;

for(i=1;i<n;i++){ // tim cac dinh ke cac dinh da co

if(visited[i]==0&&a[i][v]<distance[i])
{
distance[i]=a[i][v];
from[i]=v;
}
}
min_cost=min_cost+a[u][v];
}
return(min_cost);
}

int main(){
int test; cin >> test;
for(int tc=1; tc <= test; tc++){
cin >> n;
for(int i=0; i< n; i++){
for(int j=0; j<n; j++){
cin >> a[i][j];
}
}
int total = prims();
cout << "Case #" << tc << endl;
cout << total << endl;
}
return 0;
}```