Форум программистов, компьютерный форум CyberForum.ru

Граф - C++

Восстановить пароль Регистрация
 
Domonion
1 / 1 / 0
Регистрация: 03.06.2013
Сообщений: 89
10.01.2014, 13:26     Граф #1
В городе N площадей. Любые две площади соединены между собой ровно одной дорогой с двусторонним движением. В этом городе живет Штирлиц. У Штирлица есть хобби - он любит воскресным утром выйти из дома, сесть в машину, выбрать какой-нибудь кольцевой маршрут, проходящий ровно по трем площадям (то есть сначала он едет с какой-то площади на какую-то другую, потом - на третью, затем возвращается на начальную, и опять едет по этому маршруту). Он воображает, что где-то на этом пути стоит Борман. И так вот ездит Штирлиц все воскресенье, пока голова не закружится, и радуется...

Естественно, что Штирлицу хочется проезжать мимо точки, в которой, как он воображает, стоит Борман, как можно чаще. Для этого, естественно, выбранный Штирлицем маршрут должен быть как можно короче. Напишите программу, которая выберет оптимальный для Штирлица маршрут.

Формат входных данных
В первой строке задается число N (3 <= N <= 100). В последующих строках содержится матрица NxN расстояний между площадями (число в позиции i,j обозначает длину дороги, соединяющей i-ую и j-ую площади). Все числа в матрице (кроме стоящих на главной диагонали) - натуральные, не превышающие 1000. Матрица симметрична относительно главной диагонали, на главной диагонали стоят 0.

Формат выходных данных
Требуется вывести номера площадей в оптимальном маршруте. Если маршрутов несколько, выведите любой из них.

Пример

Входные данные
5
0 20 10 30 40
20 0 30 1 2
10 30 0 40 1000
30 1 40 0 21
40 2 1000 21 0

Добавлено через 1 час 52 минуты
UP.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.01.2014, 13:26     Граф
Посмотрите здесь:

C++ Граф
Граф C++
C++ Граф
Граф C++
C++ Граф в С
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
10.01.2014, 13:37     Граф #2
Самое простое для реализации (и для гугления) алгоритм Дейкстры или Флойда — Уоршелла. Можно нагуглить готовый код на С/С++.
Qwertiy
817 / 625 / 75
Регистрация: 20.08.2013
Сообщений: 2,525
10.01.2014, 13:46     Граф #3
Цитата Сообщение от Kastaneda Посмотреть сообщение
Самое простое для реализации (и для гугления) алгоритм Дейкстры или Флойда — Уоршелла.
Да ладно. Искать таким образом кратчайший цикл длины 3 в полном графе - это полнейшее извращение.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
10.01.2014, 13:50     Граф #4
Цитата Сообщение от Qwertiy Посмотреть сообщение
Искать таким образом кратчайший цикл длины 3 в полном графе - это полнейшее извращение.
Возможно, я теорию/алгоритмы графов плохо знаю. С предложенными алгоритмами просто на днях столкнулся, поэтому предложил как вариант, они действительно простые.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
10.01.2014, 14:06     Граф #5
Цитата Сообщение от Kastaneda Посмотреть сообщение
Самое простое для реализации (и для гугления) алгоритм Дейкстры или Флойда — Уоршелла.
флойд и дейкстра здесь не нужны, т.к. для решения задачи нужно найти все пути длиной 1 ребро, а эта информация уже известна из матрицы смежности. здесь достаточно просто перебрать все возможные тройки вершин.
Qwertiy
817 / 625 / 75
Регистрация: 20.08.2013
Сообщений: 2,525
10.01.2014, 14:10     Граф #6
Зачем тут вообще графовые алгоритмы?

C++
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
#define _CRT_SECURE_NO_WARNINGS
 
#include <cstdio>
 
//int $((freopen("input.txt","r",stdin),/*freopen("output.txt","w",stdout),*/0));
 
#define MAXN 128
 
unsigned g[MAXN][MAXN];
 
int main(void)
{
  unsigned n, q, w, e, cur, a, b, c, best;
 
  scanf("%u", &n);
  for(q=0; q<n; ++q)
    for(w=0; w<n; ++w)
      scanf("%u", g[q]+w);
 
  best=~0U;
  for(q=0; q<n; ++q)
    for(w=0; w<n; ++w)
      if(q!=w)
        for(e=0; e<n; ++e)
          if(e!=w && e!=q && (cur=g[q][w]+g[w][e]+g[e][q])<best)
            best=cur, a=q, b=w, c=e;
 
  printf("Cycle %u -> %u -> %u -> %u has length %u\n", a+1, b+1, c+1, a+1, best);
 
  return 0;
}
Для неориентированных графов можно немного соптимизировать циклы.

Добавлено через 1 минуту
Цитата Сообщение от ya_noob Посмотреть сообщение
здесь достаточно просто перебрать все возможные тройки вершин.
Ага.
Yandex
Объявления
10.01.2014, 14:10     Граф
Ответ Создать тему
Опции темы

Текущее время: 21:56. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru