Поиск двух городов в системе двусторонних дорог и соединяющего пути длиной не более 100 км, проходящего через каждую дорогу ровно 1 раз

1. Условие задачи

Задача №32 Задана система двусторонних дорог. Найти два города и соединяющий их путь длиной не более 100 км, проходящий через каждую дорогу ровно 1 раз.

2. Анализ задачи

Дано:

Множество вершин и ребер, каждое из которых имеет свой вес, т.е. взвешенный граф (G, w), где G(V,E) - граф, а w : E_G -> Z – функция, ставящая в соответствие каждому ребру e число w(e).

Результат:

Две вершины и множество вершин {u₁… u_n}, которые образуют эйлерову цепь между ними длиной не более 100 км, либо сообщение об отсутствии решения.

Метод решения:

Т.к. по условию задачи нужно найти цепь, содержащую каждое ребро 1 раз, то эта цепь будет эйлеровой.

Для того чтобы узнать, можно ли в данном графе построить эйлерову цепь нужной длины, нужно проверить выполнение следующих условий:

·  В графе должно быть ровно 2 вершины нечетной степени (которые и будут являться искомыми городами)

·  Граф связен (не беря в расчет изолированных вершин, т.е., по условию задачи, городов, к которым дорог не подходит)

·  Сумма весов всех ребер не должна превышать 100

·  В графе должно быть не меньше 2 неизолированных вершин

Если эти условия выполняются, значит задача имеет решение, которое сводится к построению эйлеровой цепи между двумя вершинами нечетной степени.

Для определения связности графа будем обходить граф начиная с любой вершины, попутно помечая пройденные. Если все вершины кроме изолированных помечены, значит условие выполняется.

Эйлерова цепь представляет собой простую цепь (без циклов), и включенные в нее циклы. Следовательно, нам нужно провести цепь между двумя выбранными вершинами, а потом искать петли, которые будут к ней примыкать.

3.  Алгоритм:

Алгоритм определения связности графа:

void nxt(int s)

{       

int i;

   if (adj[s][s]!=2) //Если вершине не помечена

   {    

adj[s][s] = 2; //Пометим

         for (i=0; i<n; i++) //Пойдем помечать все смежные с ней

         {    

if ((adj[s][i]>0) && (adj[i][i]!=2)) //Крометех, чтоуже            nxt(i);                            // помечены

         }

   }

}

Строить эйлерову цепь будем по следующему алгоритму:

Исходные данные:

v – начальная вершина, adj[i] – множество вершин, смежных с вершиной i

Z = {v}; //Начало строящейся эйлеровой цепи

R = Æ;  //Частный расширяющийся цикл эйлеровой цепи

do

{

   R = {v}; //Построение отдельного цикла эйлеровой цепи

   do

   {

      w=adj[v];

      R = R È {w};

adj[v] = adj[v] \ {w};

if (v ¹ w)

adj[w] = adj[w] \ {v}; //Удаление пройденного ребра (v,w)

   } while (|adj[v]|>0) //Пока все ребра не пройдены

   Z = Z È R; //Объединение циклов в 1 цикл

} while ( !$vÎZ : |adj[v]|>0 )

Полученное множество Z и будет искомой цепью.

Представление исходных данных и результата:

Информация вводится из файла (input.txt), в котором указано кол-во вершин и все ребра с их весами. Такое представление, в отличие от матрицы смежности или списка смежности, наиболее удобно для пользователя.

Формат входного файла следующий:

<n>

<v₁>-<v₂> <w₁₂>

. . .

<v_i>-<v_j> <w_ij>

где <n> - кол-во вершин в графе, v_i – вершины, <v_i>-<v_j> - ребра, а <w_ij> - вес соответствующего ребра. Вершины должны быть занумерованы по порядку начиная с нулевой.

Если после работы программы было найдено решение, то об этом сообщается пользователю, и само решение записывается в файл output.txt (в виде последовательности вершин), иначе, сообщается об отсутствии решения.

Внутреннее представление и структуры данных:

Граф в программе мы будем представлять матрицей смежности, т.е. целочисленным двумерным массивом. Из этого следует, что количество вершин в исходном графе не может быть больше размерности массива, которая, в свою очередь, задается константой в программе. Другие структуры данных не используются.

4.  Текст программы

#include "stdio.h"

#include "iostream.h"

#include "conio.h"

#include "string.h"

#include "io.h"

#define N 20 //Максимальное кол-во вершин

int adj[N][N]; //Матрица смежности

int n; //Кол-во вершин

struct v_l

{

            int v;

            v_l *nxt;

};

v_l *add(v_l *l, int d)

{

            l->nxt = new v_l;

            l = l->nxt;

            l->v = d;

            l->nxt = NULL;

            return l;

}

int input() //Ввод данных из файла

{

            FILE *f;

            f = fopen("input.txt", "rt");

            if (f)

            {

               int n, i, j, w;

               fscanf(f, "%d", &n); //Читаем кол-во вершин

               for (i=0; i<n; i++)

               for (j=0; j<n; j++)

               adj[i][j] = 0; //Инициализация массива

               while (!feof(f))

               {

                     fscanf(f, "%d-%d %d", &i, &j, &w); //Читаем ребра и их веса

                     if ((i<n) && (j<n))

                     adj[i][j] = adj[j][i] = w;

                     else

                     {