Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.57/7: Рейтинг темы: голосов - 7, средняя оценка - 4.57
Zivaka
0 / 0 / 0
Регистрация: 02.11.2014
Сообщений: 21
1

Для любителей графов

30.03.2015, 18:59. Просмотров 1287. Ответов 3
Метки нет (Все метки)

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

Требуется написать программу, которая поможет Ивану Ивановичу точно определить может ли выиграть выбранная им лошадь.


Входной текстовый файл содержит в первой строке два целых числа N (1 <= N <= 100) и K (1 <= K <= N), где N - количество лошадей, принимающих участие в скачках, K - номер лошади, на которую хочет сделать ставку Иван Иванович. Следующие строки содержат по два числа X и Y (1 <= X, Y <= N), обозначающие, что лошадь с номером X быстрее лошади с номером Y. Пары X и Y не повторяются. Набор данных завершается строкой, содержащей единственный ноль. Эту строку обрабатывать не надо.
Гарантируется, что информация, раздобытая Иваном Ивановичем, корректна.
Выходной текстовый файл должен содержать слово "Yes" без кавычек, если Иван Иванович уверен в своем выигрыше. В противном случае выведите "No" без кавычек.

Пример:
1 тест
5 5
1 2
2 3
3 4
5 1
0

Yes

2 тест
4 2
2 3
4 1
0

No
3 тест
3 1
1 2
3 2
0

No


Помогите придумать, как использовать графы.
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.03.2015, 18:59
Ответы с готовыми решениями:

Теорие графов. Композиция двух неор. графов.
Здравствуйте. Прошу помощи уже здесь :| (old topic)... Прошу помочь с...

Алгоритм Джонсона для графов
Подскажите, пожалуйста, где можно найти реализацию этого алгоритма или помогите...

Для заданных двух графов построить их соединение
добрый день! помогите решить задачу: Соединением графов G1 и G2 называется...

Программа для построения графов. Как запустить созданный файл в graphviz?
Необходимо создать программу, которая будет обрабатывать матрицу смежности...

Теория графов
Есть задание. найти максимальное и среднее расстояние между центральными...

3
dmitrydm
0 / 0 / 0
Регистрация: 30.03.2015
Сообщений: 8
30.03.2015, 23:35 2
задали именно эту задачу! присоединяюсь и прошу помочь!
0
mat_for_c
217 / 210 / 77
Регистрация: 26.04.2013
Сообщений: 963
Завершенные тесты: 3
31.03.2015, 00:40 3
Лучший ответ Сообщение было отмечено Zivaka как решение

Решение

Расскажу идею.
Пусть лошадь А быстрее лошади Б. Тогда для графа будет существовать дуга от вершины А к вершине Б. Граф представляется в виде квадратной несимметричной матрицы (0 - нет дуги, 1 - есть дуга, диагональ - 0).
Если ставка идет на лошадь Х, то нам нужно проверить, возможно ли посетить из вершины Х все остальные вершины. Если это возможно, то тогда лошадь Х самая быстрая, иначе непонятно, то бишь "No".
1
Zivaka
0 / 0 / 0
Регистрация: 02.11.2014
Сообщений: 21
01.04.2015, 22:12  [ТС] 4
Как-то так получилось, кому интересно.
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
int n;
vector <bool> v(110, false);
 
void dfs(vector <vector<int> >& a, int x)
{
    v[x] = true;
 
    for (int i = 0; i<n; i++)
        if (a[x][i] == 1 && !v[i])
            dfs(a, i);
 
}
 
int main()
{
    int k;
    cin >> n >> k;
    k--;
    vector < vector<int> > a(n, vector<int>(n, 0));
    while (true)
    {
        int x, y;
        cin >> x;
        if (x == 0) break;
        cin >> y;
        a[x - 1][y - 1] = 1;
    }
 
    dfs(a, k);
    v[k] = 1;
    for (int i = 0; i<n; i++)
        if (!v[i])
        {
            cout << "No";
            return 0;
        }
    cout << "Yes";
    return 0;
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.04.2015, 22:12

Визуализация графов
В общем есть такой пакет http://ru.wikipedia.org/wiki/Graphviz С помощью...

Представление графов С++
#include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; int n; int...

Представление графов С++
Считывания графу из входного файла. На вход подается текстовый файл следующего...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

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