/*

VU THI DIEU_ K52A2 TOAN TIN

YEU CAU : tim va tinh do dai cua cay bao trum nho nhat = thuat toan PRIM

*/

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#define vocung 1000

int a[100][100],M[100],pr[100],d[100],n;

void nhap()

{

int i,j,k;

FILE*f;

f=fopen("prim.inp","r");

fscanf(f,"%d",&n);

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

{

fscanf(f,"%d",&k);

a[i][j]=k;

}

fclose(f);

}

void khoitao()

{

for(i=1;i<=n;i++)

{

pr[i]=1;

d[i]=a[1][i];

M[i]=0;

}

M[1]=1;

}

int mind()

{

int vt=1;

int gt=vocung;

for(i=1;i<=n;i++)

{

if(M[i]==0 && d[i] < gt)

{

gt=d[i];

vt=i;

}

}

return vt;

}

void prim()

{

int i,j,t;

for(t=1;t<=n;t++)

{

i=mind();

M[i]=1;

for(j=1;j<=n;j++)

if(M[j]==0 && d[j] > a[i][j])

{

d[j]=a[i][j];

pr[j]=i;

}

}

}

void inkq()

{FILE *f;

f=fopen("Graph.out","w+");

for(i=1;i<=n;i++)

{

fprintf(f,"(%d ,%d )",i,pr[i]);

}

fclose(f);

}

{//FILE *f;

//f=fopen("Graph.out","w+");

int s=0;

for(int i=1;i<=n;i++)

s+=d[i];

return s;

// fprintf(f,"%3d",tong());

}

//fclose(f);}

int main()

{

nhap();

khoitao();

// printf("cay bao trum nho nhat la :

");

inkq();

printf("All completed!");

getch();

return 0;

}