# Well Project

unknown
plain_text
a month ago
2.6 kB
1
Indexable
Never
```#define _CRT_SECURE_NO_WARNINGS
#define SIZE 109

#include<iostream>

using namespace std;

int visit[SIZE];
int A[SIZE][SIZE];
int countdown;
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) {

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;
}
}
}
}
}
visit[jmini] = 1;
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;
}```