Code:
#include <stdio.h>
#include <stdlib.h>
int** make_2D_array(int array_size_x,int array_size_y)
{
int i;
int** Array;
Array = (int**) malloc(array_size_x*sizeof(int*));
if(Array==NULL){
free(Array);
printf("Error allocating memory\n");
return 1;
}
for (i = 0; i < array_size_x; i++){
Array[i] = (int*) malloc(array_size_y*sizeof(int));
if(Array[i]==NULL){
free(Array[i]);
printf("Error allocating memory\n");
return 1;
}
}
return Array;
}
int find_min(int *Aarray[],int Barray[],int n,int max,int *pointA,int *pointB)
{
int min=max+1,i,j;
for(i=0;i<n;i++){
for(j=0;j<Barray[i];j++){
if(Aarray[i][j]<min){
min=Aarray[i][j];
*pointA=i;
*pointB=j;
}
}
}
return min;
}
int find_max(int *Aarray[],int Barray[],int n)
{
int max=Aarray[0][0],i,j;
for(i=0;i<n;i++){
for(j=0;j<Barray[i];j++){
if(Aarray[i][j]>max){
max=Aarray[i][j];
}
}
}
return max;
}
int main()
{
int **connection,**weight,i,j,n,*number=NULL;
do{
printf("Enter the number of points\n");
scanf("%d",&n);
} while(n%2==1);
connection=make_2D_array(n,n-1);
weight=make_2D_array(n,n-1);
number=malloc(n*sizeof(int));
if(number==NULL){
free(number);
printf("Error allocating memory\n");
return 1;
}
for(i=0;i<n;i++){
do{
printf("Enter the number of points that the %d point is connected with\n",i+1);
scanf("%d",&number[i]);
} while(number[i]>=n || number[i]<1);
for(j=0;j<number[i];j++){
do{
printf("Enter the %d point that is connected with\n",j+1);
scanf("%d",&connection[i][j]);
} while(connection[i][j]<0);
do{
printf("Enter the weight of the bar between those two points\n");
scanf("%d",&weight[i][j]);
} while(weight[i][j]<1);
}
}
int k,l,min,max,pointA,pointB,sum=0,*A,*B;
/* Για να διαγραφω τις κορυφες που περναω στους πινακες Α και Β θα βρω πρωτα το max του weight και επειτα
θα βαζω στα κελια των κορυφων που θελω να διαγραψω την τιμη max+1 */
A=malloc(n/2*sizeof(int));
B=malloc(n/2*sizeof(int));
max=find_max(weight,number,n);
for(i=0;i<n/2;i++){
/*Βάζω στα κελιά την τιμή max + 2. Μετά όταν πάω και ψάχνω το ελάχιστο αρχικοποιώ το min ως max + 1.
Αν τελειώσει η αναζήτηση και ο min είναι ακόμα max +1 τότε το πρόγραμμα θα έχει αποτύχει. Όταν "διαγράφω" τις
κορυφές α και β (για παράδειγμα) μετά πάω στις γραμμές α και β του weight και "διαγράφω" όλα τα στοιχεία τους
(τα κάνω δηλαδή max + 2).Μετά πάω στον connection και ψάχνω όλον τον πίνακα και όπους βρω στοιχείο ίσο με
α ή β, πάω στην αντίστοιχη θέση του weight και το κάνω και αυτό max + 2. Γιατί για παράδειγμα η ακμή με το μικρότερο
βαρος μπορει να ήταν μεταξύ των κορυφών 1 και 2 και η αμέσως επόμενη μεταξύ των κορυφών 1 και 3(την 1 την έχω βάλει
στην ομάδα Α, άρα δεν μπορώ να την χρησιμοποιήσω ξανά). */
min=find_min(weight,number,n,max,pointA,pointB);
if(min==max+1){
printf("The program failed\n");
return 1;
} else {
A[i]=pointA;
B[i]=connection[pointA][pointB];
sum += weight[pointA][pointB];
weight[pointA][pointB]=max+2;
for(k=0;k<n;k++){
for(l=0;l<n-1;l++){
if(connection[k][l]==pointA || connection[k][l]==connection[pointA][pointB]){
weight[k][l]=max+2;
}
}
}
}
}
printf("Array A\n");
for(i=0;i<n/2;i++){
printf("%d\n",&A[i]);
}
printf("\n");
printf("Array B\n");
for(i=0;i<n/2;i++){
printf("%d\n",&B[i]);
}
printf("\n");
printf("The sum is %d\n",sum);
for (i = 0; i < n; i++){
free(connection[i]);
free(weight[i]);
}
free(connection);
free(weight);
free(A);
free(B);
free(number);
return 0;
}