include stdio include stdlib include string define INF 100 define LEN

#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;
}