fr.c
#include <stdio.h>
#include <string.h>
#define MAX 1010
char matrix[MAX][MAX] = {{0}};
int children[MAX][MAX] = {{0}};
int parents[MAX] = {0};
int weights[MAX] = {0};
int no_children[MAX] = {0};
int n = 0, c = 0, i = 0, j = 0, k = 0, w, pi;
void construct(int node) {
int i;
for(i=0; i<MAX; i++) {
if(matrix[node][i] > 0) {
parents[i] = node;
children[node][no_children[node]] = i;
no_children[node]++;
weights[i] = matrix[i][node];
matrix[i][node] = 0;
construct(i);
}
}
}
int main() {
while(1) {
for(i=0; i<n-1; i++) {
matrix[j][k] = w;
matrix[k][j] = w;
}
construct(c);
do {
k = 0;
for(i=0; i<MAX; i++) {
if(no_children[i] == 0 && weights[i] > 0) {
k++; // list found?
pi = parents[i];
w = 0; j = 0;
while(1){
if(children[pi][j] == 0) break;
w += weights[children[pi][j]];
no_children[j] = -1;
j++;
}
if(w < weights[pi]) weights[pi] = w;
no_children[pi] = 0;
}
}
}while(k > 2);
j = 0; w = 0;
while(1) {
if(children[c][j] == 0) break;
w += weights[children[c][j]];
j++;
}
}
return 0;
}