#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF 100
#define LEN 4
int C[][4] = {
{INF, 15, 5, 2},
{10, INF, 3, 20},
{16, 8, INF, 5},
{2, 3, 2, INF}
};
typedef struct node {
struct node *left, *right, *parent;
int weight, from, to, **matrix, len, *rows_indexes, *colls_indexes;
} node;
node *cur_n;
int min_weight;
void search_min(node *n) {
if (n->right == NULL) {//это должен быть ЛИСТ, в не узел
if (n->weight < min_weight) {
min_weight = n->weight;
cur_n = n;
}
return;
}
search_min(n->left);
search_min(n->right);
}
int reduct(int **matrix, int len) {//приведение матрицы
int min_el, i, i1, sum_ms = 0;
for (i = 0; i < len; i++) { //обходим все строки
min_el = INF; //обнуляем
for (i1 = 0; i1 < len; i1++)
if (matrix[i][i1] < min_el) min_el = matrix[i][i1]; //находим минимум для строки
sum_ms += min_el;
for (i1 = 0; i1 < len; i1++) if (matrix[i][i1] != INF) matrix[i][i1] -= min_el; //вычитаем минимум с элементов строки
}
for (i = 0; i < len; i++) { //обходим все столбцы матрицы
min_el = INF;
for (i1 = 0; i1 < len; i1++)
if (matrix[i1][i] < min_el) min_el = matrix[i1][i]; //находим минимум для столбца
sum_ms += min_el;
for (i1 = 0; i1 < len; i1++) if (matrix[i1][i] != INF) matrix[i1][i] -= min_el;
}
return sum_ms; //возвращаем сумму приведения
}
void clear_tree(node *n) {
if (n == NULL) return;
clear_tree(n->left);
clear_tree(n->right);
if (n->matrix != NULL) {
int i;
cur_n = n->parent;
while (n->rows_indexes == cur_n->rows_indexes) {//для лев. узлов в которых ссылки на род. элем.
cur_n->matrix = NULL;
if ((cur_n = cur_n->parent) == NULL) break;
}
for (i = 0; i < n->len; i++) free((n->matrix)[i]); //чистим главную матрицу
free(n->matrix);
free(n->rows_indexes);
free(n->colls_indexes);
}
free(n); //удал. сам узел
}
int main() {
node* tree = (node*) malloc(sizeof (node)); //корень всего дерева
int i, i1, j, j1;
//инициализация главного корня
tree->matrix = (int**) malloc(sizeof (int*)*LEN);
tree->len = LEN;
tree->rows_indexes = (int*) malloc(sizeof (int)*LEN);
tree->colls_indexes = (int*) malloc(sizeof (int)*LEN);
for (i = 0; i < LEN; i++) {
(tree->matrix)[i] = (int*) malloc(sizeof (int)*LEN);
memcpy((tree->matrix)[i], C[i], sizeof (int)*LEN);
(tree->rows_indexes)[i] = (tree->colls_indexes)[i] = i; //у базового узла индексы будут обычными
}
tree->weight = reduct(tree->matrix, tree->len);
tree->parent = NULL;
cur_n = tree; //текущий узел
node *temp_n; //для поиска пути
int zero_weight, //тут будет хранится вес нуля
max_zero_weight, //тут будет макс. вес нуля
min_el_coll, min_el_row,
from, to; //относительные координаты точек начала и конца пути соответсвенно
while (1) {
cur_n->left = (node*) malloc(sizeof (node));
cur_n->right = (node*) malloc(sizeof (node));
cur_n->right->parent = cur_n->left->parent = cur_n; //определяем родителя
cur_n->left->left = cur_n->left->right = cur_n->right->left = cur_n->right->right = NULL;
if (cur_n->len == 2) {//формируем "плоды"
cur_n->left->from = (cur_n->rows_indexes)[0];
cur_n->right->from = (cur_n->rows_indexes)[1];
cur_n->left->matrix = cur_n->right->matrix = NULL;
if ((cur_n->matrix)[0][0] == INF) {
cur_n->left->to = (cur_n->colls_indexes)[1];
cur_n->right->to = (cur_n->colls_indexes)[0];
} else {
cur_n->left->to = (cur_n->colls_indexes)[0];
cur_n->right->to = (cur_n->colls_indexes)[1];
}
break; //завершаем обход и переходим к выводу результата
}
cur_n->left->matrix = cur_n->matrix; //определяем матрицу для левого узла
cur_n->left->len = cur_n->len;
cur_n->left->rows_indexes = cur_n->rows_indexes;
cur_n->left->colls_indexes = cur_n->colls_indexes;
max_zero_weight = 0;
for (i = 0; i < cur_n->len; i++)//находим нуль с наибольшим весом
for (i1 = 0; i1 < cur_n->len; i1++) {
if ((cur_n->matrix)[i][i1] != 0) continue;
min_el_coll = min_el_row = INF;
for (j = 0; j < cur_n->len; j++) {
if (j != i1 && (cur_n->matrix)[i][j] < min_el_row) min_el_row = (cur_n->matrix)[i][j];
if (j != i && (cur_n->matrix)[j][i1] < min_el_coll) min_el_coll = (cur_n->matrix)[j][i1];
}
zero_weight = min_el_row + min_el_coll;
if (zero_weight > max_zero_weight) {//определяем координаты нуля с наибольшим весом
from = i, to = i1;
max_zero_weight = zero_weight;
}
}
cur_n->left->weight = (cur_n->weight) + max_zero_weight; //определем вес левого узла
cur_n->right->len = (cur_n->len) - 1; //задаем размерность нового массива
cur_n->right->rows_indexes = (int*) malloc(sizeof (int)*cur_n->right->len); //индексов будет на 1 меньше
cur_n->right->colls_indexes = (int*) malloc(sizeof (int)*cur_n->right->len);
cur_n->right->matrix = (int**) malloc(sizeof (int*)*cur_n->right->len); //новый массив будет на 1 строку короче
for (i = 0, i1 = 0; i < (cur_n->len); i++) {//тут мы формируем новую матрицу с вычеркнутыми столб. и стр.
if (i == from) continue; //этой строки не будет в новом массиве
(cur_n->right->rows_indexes)[i1] = (cur_n->rows_indexes)[i]; //заполнение нового масс. индкс. стр.
(cur_n->right->matrix)[i1] = (int*) malloc(sizeof (int)*cur_n->right->len); //новая строка матрицы
for (j = 0, j1 = 0; j < cur_n->len; j++) {
if (j == to) continue;
(cur_n->right->colls_indexes)[j1] = (cur_n->colls_indexes)[j]; //заполнение нового масс. индкс. столб.
(cur_n->right->matrix)[i1][j1] = (cur_n->matrix)[i][j];
j1++;
}
i1++;
}
(cur_n->left->matrix)[from][to] = INF;
from = cur_n->left->from = cur_n->right->from = (cur_n->rows_indexes)[from]; //абсолютный индекс
to = cur_n->left->to = cur_n->right->to = (cur_n->colls_indexes)[to];
temp_n = cur_n;
while (temp_n != tree) {//обходим всех родителей для форм. пути
if (temp_n->matrix != temp_n->parent->matrix) {//должна быть точка ВКЛЮЧЕНИЯ
if (temp_n->from == to) {//тут уже будут абсолют. коорд.
to = temp_n->to;
temp_n = cur_n; //начинаем обход заново
continue;
}
if (temp_n->to == from) {
from = temp_n->from;
temp_n = cur_n; //начинаем обход заново
continue;
}
}
temp_n = temp_n->parent;
}
for (i = 0; i < cur_n->right->len; i++) {//формируем относительные коорд.
if ((cur_n->right->colls_indexes)[i] == from) j1 = i;
if ((cur_n->right->rows_indexes)[i] == to) i1 = i;
}
(cur_n->right->matrix)[i1][j1] = INF; //запрещаем возврат в правой матрице
cur_n->right->weight = cur_n->weight + reduct(cur_n->right->matrix, cur_n->right->len); //приведем вновь образ. матрицу
reduct(cur_n->left->matrix, cur_n->left->len); //приведем левую матрицу
min_weight = INF;
search_min(tree); //ищем узел с наим. весом
}
from = cur_n->left->from;
to = cur_n->left->to;
printf("Result is: \n{%d, %d", from, to); //выводим начало контура
temp_n = cur_n->right; //начинаем обход с правого "плода"
while (temp_n != tree) {//формируем результат
if (temp_n->matrix != temp_n->parent->matrix) {
if (temp_n->from == to) {
to = temp_n->to;
printf(", %d", to);
temp_n = cur_n->right; //начинаем обход заново
continue;
}
}
temp_n = temp_n->parent;
}
printf("}\nweight = %d", cur_n->weight);
clear_tree(tree); //чистим все дерево
return 0;
}