Well Project

#define _CRT_SECURE_NO_WARNINGS
#define SIZE 109

#include<iostream>

using namespace std;

int visit[SIZE];
int A[SIZE][SIZE];
int countdown;
int Answer;
int i, j;
int mini;
int jmini;

int main(int argc, char** argv) {
	int test_case;
	int T, N;

	//ios::sync_with_stdio(false);

	freopen("Well Project.txt", "r", stdin);
	cin >> T;

	for (test_case = 1; test_case <= T; ++test_case) {
		Answer = 0;

		cin >> N;
		for (i = 1; i <= N; i++) {
			for (j = 1; j <= N; j++) {
				cin >> A[i][j];
			}
			visit[i] = 0;
		}

		// PRIM
		// Add 1st vertex to MST
		visit[1] = 1;
		countdown = 1;
		//Add one by one vertex to MST
		while (countdown < N) {
			//Find the minimum weight vertex
			mini = 1000000;
			for (i = 1; i <= N; i++) {
				if (visit[i] == 1) {
					for (j = 1; j <= N; j++) {
						if (j != i && !visit[j]) {
							if (A[i][j] < mini) {
								mini = A[i][j];
								jmini = j;
							}
						}
					}
				}
			}
			//Add found vertex
			visit[jmini] = 1;
			Answer += mini;
			countdown++;
		}


		// Print the answer to standard output(screen).
		cout << "Case #" << test_case << endl << Answer << endl;
	}
	//while(1);
	return 0;//Your program should return 0 on normal termination.
}















#include<iostream>
using namespace std;
#define N 101
int T, n, a[N][N];
int st[N*N];
int en[N*N];
int dist[N*N];
int parent[N];
int edge;

int findSet(int x)
{
	if(x==parent[x]) return x;
	return parent[x]=findSet(parent[x]);
}

void swap(int i, int j)
{
	int tmp=st[i]; st[i]=st[j]; st[j]=tmp;
	 tmp=en[i]; en[i]=en[j]; en[j]=tmp;
	 tmp=dist[i]; dist[i]=dist[j]; dist[j]=tmp;
}

void sort()
{
	for(int i=0;i<edge-1;i++)
		for(int j=i+1;j<edge;j++)
			if(dist[i]>dist[j])
				swap(i,j);
}

void makeSet(int x)
{
	parent[x]=x;
}

void join(int x, int y)
{
	parent[findSet(y)] = findSet(x);
}

int main()
{
	freopen("a.txt","r",stdin);
	cin>>T;
	for(int tc=1;tc<=T;tc++)
	{
		cin>>n;
		edge=0;
		for(int i=0;i<n;i++)
		{
			//parent[i]=i;
			makeSet(i);
			for(int j=0;j<n;j++)
			{
				cin>>a[i][j];
			}
		}

		for(int i=0;i<n;i++)
		{
			for(int j=i+1;j<n;j++)
			{
				
					dist[edge]=a[i][j];
					st[edge]=i;
					en[edge++]=j;
				
			}
		}
		int ans=0;
		sort();
		for(int i=0;i<edge;i++)
		{
			int u=findSet(st[i]);
			int v=findSet(en[i]);
			if(u==v)
				continue;
			else
			{
				ans+=dist[i];
				join(u,v);
			}
		}

		cout<<"Case #"<<tc<<endl<<ans<<endl;

	}
	return 0;
}