Untitled

mail@pastecode.io avatar
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;
}