5.2. 박인서 ¶
- Minimum Spanning Tree
- 입력 예
- 입력 예
1 2 2 1 3 2 2 4 4 3 4 1 2 7 1 3 7 5 3 6 2 6 7 4 3 5 3 5 6 3
- 출력 예 : 11
- 소스
#include <stdio.h>
#define LEN 11
int a[LEN][3],ver[LEN];
int oper(int a,int b)
{
if(a==0 && b==1) return 1;
if(a==1 && b==0) return 1;
return 0;
}
int main()
{
int i,min[3]={0,0,100},res=0;
for(i=0;i<10;i++) scanf("%d %d %d",&a[i][0],&a[i][1],&a[i][2]);
ver[1]=1;
while(1)
{
min[2]=100;
for(i=0;i<10;i++)
{
if(oper(ver[a[i][0]], ver[a[i][1]]) && a[i][2]<min[2]) min[0]=a[i][0],min[1]=a[i][1],min[2]=a[i][2];
}
if(min[2]==100) break;
ver[min[0]]=1,ver[min[1]]=1;
res+=min[2];
}
printf("%d",res);
return 0;
}
5.3. 이원준 ¶
#include<stdio.h>
void MST(int S[], int E[], int N[]){
int temp[7];
int ntemp[6] = { 0 };
int i, j, k, m;
int mini = 0;
int mnum;
int flag = 0;
int f = 0;
temp[0] = 5;
for (i = 0; i < 7; i++){
mini = 0;
for (j = 0; j < 10; j++){
for (k = 0; k < i; k++){
if (S[j] == temp[k]){
for (m = 0; m < i; m++){
if (E[j] == temp[m]){
flag = 1;
break;
}
}
if (flag == 0){
if (mini == 0){
temp[i] = E[j];
ntemp[i-1] = j;
mini = N[j];
}
else if (mini > N[j]){
temp[i] = E[j];
ntemp[i-1] = j;
mini = N[j];
}
}
flag = 0;
}
if (E[j] == temp[k]){
for (m = 0; m < i; m++){
if (S[j] == temp[m]){
flag = 1;
break;
}
}
if (flag == 0){
if (mini == 0){
temp[i] = S[j];
ntemp[i-1] = j;
mini = N[j];
}
else if (mini > N[j]){
temp[i] = S[j];
ntemp[i-1] = j;
mini = N[j];
}
}
flag = 0;
}
}
}
}
k = 1;
for (i = 0; i < 6; i++){
f += N[ntemp[i]];
}
printf("%d", f);
}
void main(){
int S[10];
int E[10];
int N[10];
S[0] = 1;
E[0] = 3;
N[0] = 2;
S[1] = 1;
E[1] = 2;
N[1] = 2;
S[2] = 2;
E[2] = 4;
N[2] = 4;
S[3] = 2;
E[3] = 7;
N[3] = 6;
S[4] = 3;
E[4] = 4;
N[4] = 1;
S[5] = 3;
E[5] = 7;
N[5] = 7;
S[6] = 3;
E[6] = 5;
N[6] = 3;
S[7] = 3;
E[7] = 6;
N[7] = 2;
S[8] = 5;
E[8] = 6;
N[8] = 3;
S[9] = 6;
E[9] = 7;
N[9] = 8;
MST(S, E, N);
}
