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

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

Войти
Регистрация
Восстановить пароль
 
Arantir1
Сообщений: n/a
#1

Цикл отрицательного веса - C++

27.12.2013, 00:38. Просмотров 777. Ответов 0
Метки нет (Все метки)

Помогите переделать решение, нашёл в интернете, но оно немного не подходит, а я никак не могу разобраться в коде и, следовательно, что-либо изменить. Можно обойтись без проверок, но очень помогли бы хоть какие-нибудь комментарии.

Условие:

Задан ориентированный граф, требуется определить, существует ли в нём цикл отрицательного веса. Использовать для этого метод Форда — Беллмана.

Входные данные
В первой строке входного файла содержится два целых числа n, m — число вершин и ребер графа соответственно (1 ≤ n ≤ 1000,0 ≤ m ≤ 100000). Далее следует описание m ребер графа a,b,c — ребро из вершины a в вершину b веса c (1 ≤ a,b ≤ n,−1000 ≤ c ≤ 1000).

Выходные данные
В первой строке файла выведите “YES”, если найден цикл отрицательного веса и — “NO” иначе. В случае положительного ответа далее выведите число ребер в цикле, затем номера самих ребер в порядке обхода по циклу. Ребра нумеруются с единицы в том порядке, в котором они следуют во входном файле.

Пример
Ввод
7 10
7 4 37
2 3 68
7 2 114
7 2 -69
7 2 58
1 6 112
7 6 103
2 7 -119
7 1 -107
1 5 23

Вывод
YES
2
4 8

Код, который я нашёл, выводит во второй строке количество вершин в искомом цикле (считая одинаковые первую и последнюю), а в третьей строке - вершины, входящие в этот цикл, в порядке обхода. Сделайте, пожалуйста, чтобы прога делала как у меня в условии, а то у меня уже мозг кипит. Надо было меньше пары прогуливать, тогда может и понял бы. От этой проги зависит допуск к экзамену, а в ночь с пятницы на субботу приём программ прекращается.

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int inf = 1555555555;
struct edge {
        int a, b, cost;
};
int main()
{
        vector<edge> e;
        int n, m, i, ans = 0;        
    cin>>n>>m;
    edge t;
    for(i=0; i<m; i++)
        {
                cin>>t.a>>t.b>>t.cost;
        t.a--; t.b--;
        e.push_back(t);
        }
    vector<int> d (n, -1);
        vector<int> p (n);
 
        int x;
        for (int i=0; i<n; ++i) 
        {
                x = -1;
                for (int j=0; j<m; ++j)
                        if (d[e[j].a] < inf)
                                if (d[e[j].b] > d[e[j].a] + e[j].cost) 
                                {
                                        d[e[j].b] = max (-inf, d[e[j].a] + e[j].cost);
                                        p[e[j].b] = e[j].a;
                                        x = e[j].b;
                                }
        }
 
        if (x == -1)
                cout << "NO";
        else 
        {
                int y = x;
                for (int i=0; i<n; ++i)
                        y = p[y];
 
                vector<int> path;
                for (int cur=y; ; cur=p[cur]) 
                {
                        path.push_back (cur);
                        ans++;
                        if (cur == y && path.size() > 1)  break;
                }
                reverse (path.begin(), path.end());
 
                cout<<"YES"<<endl;
                cout<<ans<<endl;
                for (size_t i=0; i<path.size()-1; ++i)
                        cout << path[i]+1 << ' ';
                cout << path[path.size()-1]+1;
        }
return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.12.2013, 00:38
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Цикл отрицательного веса (C++):

Определить есть ли во взвешенном графе цикл отрицательного веса - C++
(Время: 1 сек. Память: 16 Мб Сложность: 46%) Дан взвешенный граф. Определить, есть ли в нем цикл отрицательного веса. Входные данные...

Определить номер первого отрицательного и номер последовательного отрицательного элементов массива - C++
задан массив x1,x2,...x15 определить номер первого отрицательного xi и номер последовательного отрицательного xi код я написал но ничего...

Вычисление нормального веса человека - C++
Помогите написать программу, которая вычисляет нормальный вес человека по формуле v=k*r-100, k=1.08 где k – коэффициент коррекции v...

Расчет веса геометрических фигур из различных материалов - C++
Условия задания таковы: &quot; Расчет веса геометрических фигур из различных материалов &quot;. Нужна помощь... сразу благодарю.

Почему цикл на при 1 уходит в бесконечный цикл? - C++
#define _CRT_SECURE_NO_WARNINGS #include &lt;iostream&gt; #include &lt;stdio.h&gt; #include &lt;string.h&gt; int main() { int x=0, y=0,...

Цикл: цикл for вообще никак не воспринимается транслятором - C++
Пишу программу, которая производит различные действия с одномерным массивом. Возникла следующая проблема: цикл for вообще никак не...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.12.2013, 00:38
Привет! Вот еще темы с ответами:

Перевод старинных русских мер длины торгового и аптекарского веса - C++
составьте программу перевода старинных русских мер длины торгового и аптекарского веса(счетчик цикла меняется от 1 до 10) футов в метры(1...

Установить, можно ли перевезти неделимый груз заданного веса указанными грузовиками - C++
Имеются грузовики марки МАЗ КАМАЗ КрАЗ, грузоподъемности которых соответственно G1,G2,G3. Установить, можно ли перевезти неделимый груз...

Задание на цикл с параметром и цикл с постусловием - C++
Помогите пожалуйста написать программу с этими циклами. 1. Вычислить и напечатать таблицу значений функции Z= (e^-x)sinx для 0&lt;=x&lt;=П,...

Цикл for/Цикл while Помогите срочно пожалуйста... - C++
1.Вычислить и вывести на экран в виде таблицы значения функции F от x1 до x2 с шагом dx. где a, b и c - действительные числа. 2.Цикл...


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

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

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