INFOMAN брой 17
/*
3-ти кръг на Републиканска Олимпиада по Информатика'2000
Задача 2: МАГАЗИНИ
Задача: Даден е граф с N <= 175 върха и M <= 10000 ребра. Имаме време W[i]
за което се минава един връх и R[i][j] за което се минава едно ребро. Да се
намерят такива 4 върха, че разстоянието м/у всеки два от тях да е минимално.
Разстоянието м/у два върха не включва времето за минаване на самите тях.
Вход: Изход: 18
12 16
7
9
5
1
1
2
4
2
5
3
8
8
1 2 17
1 4 4
1 9 3
1 12 9
2 6 20
2 4 1
3 6 4
3 7 9
4 6 1
4 7 11
4 8 3
5 9 8
7 8 5
8 12 2
9 11 6
10 12 5
Решение: Очевидно R[i][i] не се използва. Затова за пестене на памет ще поло-
жим: R[i][i] = W[i]. Използваме стандартния алгоритъм на Флойд (Floyd) за на-
миране разстоянията м/у всеки два върха:
Ако за произволни върхове I и J няма връзка IJ, то IJ = безкрайност
За всеки връх J прави:
За всяка двойка върхове I и K прави:
Ако IJ + JK < IK, то IK = IJ + JK
Както се вижда, алгоритъмът не е сложен. Няма да доказваме верността му,т.к.
това не е целта на текста. Естествено няма как да интерпретираме безкрайност
в C, затова имаме и една матрица edge[i][j], в която ще имаме булеви стой-
ности, показващи дали е открита връзка между i и j, по-малка от безкрайност.
Друга възможна интерпретация е да задаваме достатъчно голямо число,което със
сигурност е по-голямо от всяко възможно разстояние. Но това голямо число
трябва да е такова, че събрано няколко пъти (до N на брой), да не надвишава,
така нареченото MAX_INT. Затова и едно решение използващо втория вариант на-
малява с много областта на възможните стойности за разстоянията.
След това чрез пълно изчерпване ще намерим кои четири върха са търсените
оптимални. В използваното обхождане се използват някои оптимизации: Т.к.
R[i][j] = R[j][i] , не е необходимо да проверяваме и двете комбинации и ако
разстовнието между два или три върха е по-голямо от намереното до момента
оптимално, то със сигурност и това между четири (част от които са въпросните
два или три) пак ще бъде по-голямо.
Мартин Русков
*/
#include <stdio.h>
#define MAX_N 175
#define MAX_M 100000
unsigned int n = 12, m = 16;
int edge[MAX_N][MAX_N] =
{{ 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1 },
{ 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0 },
{ 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0 },
{ 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1 }};
unsigned int dist[MAX_N][MAX_N] =
{{ 7, 17, 0, 4, 0, 0, 0, 0, 3, 0, 0, 9 },
{ 17, 9, 0, 1, 0, 20, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 5, 0, 0, 4, 9, 0, 0, 0, 0, 0 },
{ 4, 1, 0, 1, 0, 1, 11, 3, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 1, 0, 0, 0, 8, 0, 0, 0 },
{ 0, 20, 4, 1, 0, 2, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 9, 11, 0, 0, 4, 5, 0, 0, 0, 0 },
{ 0, 0, 0, 3, 0, 0, 5, 2, 0, 0, 0, 2 },
{ 3, 0, 0, 0, 8, 0, 0, 0, 5, 0, 6, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 5 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 8, 0 },
{ 9, 0, 0, 0, 0, 0, 0, 2, 0, 5, 0, 8 }};
unsigned int min;
int main( void )
{
int i, j, k, t; // индекси
// Floyd
for( j = 0; j < n; j++ )
for( i = 0; i < n - 1; i++ )
for( k = i; k < n; k++ )
if( i != j && i != k && j != k )
if( !edge[i][k] || ( t = dist[i][j] + dist[j][j] + dist[j][k] ) < dist[i][k] )
dist[k][i] = dist[i][k] = t,
dege[i][k] = edge[k][i] = 1;
// Намиране на 4-ката чрез леко оптимизирано пълно изчерпване
min = ~0;
for( i = 0; i < n - 3; i++ )
for( j = i + 1; j < n - 2 && m < min; j++ )
{
m = dist[i][j];
for( k = j + 1; k < n - 1 && m < min; k++ )
{
m += dist[i][k] + dist[j][k];
for( t = k + 1; t < n && m < min; t++ )
{
m += dist[i][t] + dist[j][t] + dist[k][t];
if( m < min )
min = m;
m -= dist[i][t] + dist[j][t] + dist[k][t];
}
m -= dist[i][k] + dist[j][k];
}
}
printf( "%d", min );
return 0;
}