include stdio include stdlib include limits define int P_new temp int

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define N 5
int ***P, ***P_new, ***temp, **V;
int*** create_P() {
int i, j;
int ***P = (int***) malloc(sizeof (int**)*N); //массив с массивами слагемых (P1,P2,...)
for (i = 0; i < N; i++) {
P[i] = (int**) malloc(sizeof (int*)*N * N);
for (j = 0; j < N * N; j++) P[i][j] = (int*) calloc(sizeof (int), N);
}
return P;
}
void delete_P(int ***P) {
int i, j;
for (i = 0; i < N; i++) {
for (j = 0; j < N * N; j++) free(P[i][j]);
free(P[i]);
}
free(P);
}
void matrix_multiple(int i) {
int j, l, f, b1, b2;
for (j = 0, f = 0; j < N; j++) //обходим строку V и массив P; f - индекс слагаемого в P_new
if (P[j][0][0] && V[i][j]) //на ноль не умножаем
for (l = 0; P[j][l][0]; l++) {//обходим слагаемые P[j]!=0
if ((P_new[i][f][0] = V[i][j]) == (i + 1)) b1 = -1; //одна часть слагаемого
else if (P[j][l][0] != 1)
for (b1 = (V[i][j] == 1 ? 0 : 1), b2 = 0; P[j][l][b2]; b1++, b2++)
if ((P_new[i][f][b1] = P[j][l][b2]) == (i + 1)) {
b1 = -1;
break;
};
if (b1 == -1) for (b1 = 0; b1 < N; b1++) P_new[i][f][b1] = 0;
else f++;
}
if (f > 0 && b1 != -1 && f < N * N) for (j = 0; j < N; j++) P_new[i][f][j] = 0; //следующее слагаемое=0
}
int main() {
int R[N][N] = {//исходная матрица смежности весов
{-1, 7666, 68, 8, 3},
{7, -1, 145, 15, 1},
{65, 79, -1, 3, 45},
{15, 70, 5, -1, 25},
{8, 150, 60, 95, -1}
};
int i, j, m, b, min = INT_MAX, curr, min_indx = 0;
V = (int**) malloc(sizeof (int*)*N);
for (i = 0; i < N; i++) {
V[i] = (int*) malloc(sizeof (int)*N);
for (j = 0; j < N; j++) V[i][j] = (R[i][j] == -1 ? 0 : j + 1);
}
P = create_P(), P_new = create_P();
for (i = 0; i < N; i++) P[i][0][0] = (R[i][0] == -1 ? 0 : 1);
for (m = 1; m < 4; m++) {//умножаем матрицы n-1 раз
for (i = 1; i < N; i++) matrix_multiple(i);
temp = P_new;
P_new = P;
P = temp;
}
matrix_multiple(0); //для нахождения ответа находим P[0]
for (i = 0; P_new[0][i][0]; i++) {//находим кратчайший контур
curr = R[0][P_new[0][i][0] - 1];
for (j = 0; P_new[0][i][j + 1];)
curr += R[P_new[0][i][j] - 1][P_new[0][i][++j] - 1];
curr += R[P_new[0][i][j] - 1][0];
if (curr < min) {
min = curr;
min_indx = i;
}
}
printf("M={1");
for (i = 0; i < N - 1; i++) printf("%d", P_new[0][min_indx][i]);
printf("1}");
delete_P(P);
delete_P(P_new);
for (i = 0; i < N; i++) free(V[i]);
free(V);
return (0);
}