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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Domonion
1 / 1 / 0
Регистрация: 03.06.2013
Сообщений: 89
#1

Граф - C++

10.01.2014, 13:26. Просмотров 798. Ответов 5
Метки нет (Все метки)

В городе 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++
2. Имеется N населенных пунктов (N≤15), и сеть авиалиний, соединяющих эти города. Сеть задана матрицей связности M(N,N), где M(i,j) =0,...

Граф - C++
Найти все вершины неориентированного графа, к которым существует путь заданной длины от выделенной его вершины. не могу разобраться,...

Граф - C++
Дан граф в виде матрицы смежности 7х7(вводится вручную либо загружается из файла) нужно реализовать только такие функции: вычислить: ...

Граф в С - C++
Не могли бы помочь.. как можно построить граф в С ? или где модно прочесть про то как создать файл в который этот граф нарисуется?

Граф - C++
Помогите описать граф в С++ списками. По какому принципу это делается ?

Построить граф - C++
можете привести простейший пример проги которая выдаёт граф просто чертёж?

Вроде бы граф - C++
Как делается эта задачка? Сделайте пожалуйста, кто может.. Спасибо ! Дан прямоугольник MxN. Найти все варианты как можно добраться из...

подсвязный граф в си++ - C++
15.Для каждого жителя города задано множество (возможно, пустое) имен его детей; каждый житель города имеет уникальное имя. Жители x и y...

Покрашенный граф - C++
Привет для вот такого условия Дан ориентированный граф, у которого каждая дуга покрашена в один из трех цветов. Требуется найти длину...

Граф инциденций с++ - C++
В качестве расчетки было дано задание: найти граф инциденций неориентированного графа. Хотелось бы узнать, что такой граф инциденций. В...

Двудольный граф - C++
Проверить граф заданный матрицей смежности на двудольность и вывести одну из его долей

Граф - WxDev C++ - C++
Добрый вечер. Вот код графа, Писал сам. По логике вроде всё должно как бы работать. Но Выкидывает пару ошибок насчет нехватки {; Может...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kastaneda
Форумчанин
Эксперт С++
4479 / 2841 / 226
Регистрация: 12.12.2009
Сообщений: 7,222
Записей в блоге: 1
Завершенные тесты: 1
10.01.2014, 13:37     Граф #2
Самое простое для реализации (и для гугления) алгоритм Дейкстры или Флойда — Уоршелла. Можно нагуглить готовый код на С/С++.
Qwertiy
818 / 626 / 75
Регистрация: 20.08.2013
Сообщений: 2,525
10.01.2014, 13:46     Граф #3
Цитата Сообщение от Kastaneda Посмотреть сообщение
Самое простое для реализации (и для гугления) алгоритм Дейкстры или Флойда — Уоршелла.
Да ладно. Искать таким образом кратчайший цикл длины 3 в полном графе - это полнейшее извращение.
Kastaneda
Форумчанин
Эксперт С++
4479 / 2841 / 226
Регистрация: 12.12.2009
Сообщений: 7,222
Записей в блоге: 1
Завершенные тесты: 1
10.01.2014, 13:50     Граф #4
Цитата Сообщение от Qwertiy Посмотреть сообщение
Искать таким образом кратчайший цикл длины 3 в полном графе - это полнейшее извращение.
Возможно, я теорию/алгоритмы графов плохо знаю. С предложенными алгоритмами просто на днях столкнулся, поэтому предложил как вариант, они действительно простые.
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
10.01.2014, 14:06     Граф #5
Цитата Сообщение от Kastaneda Посмотреть сообщение
Самое простое для реализации (и для гугления) алгоритм Дейкстры или Флойда — Уоршелла.
флойд и дейкстра здесь не нужны, т.к. для решения задачи нужно найти все пути длиной 1 ребро, а эта информация уже известна из матрицы смежности. здесь достаточно просто перебрать все возможные тройки вершин.
Qwertiy
818 / 626 / 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     Граф
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru