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

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

Восстановить пароль Регистрация
 
Arantir1
Сообщений: n/a
27.12.2013, 00:38     Цикл отрицательного веса #1
Помогите переделать решение, нашёл в интернете, но оно немного не подходит, а я никак не могу разобраться в коде и, следовательно, что-либо изменить. Можно обойтись без проверок, но очень помогли бы хоть какие-нибудь комментарии.

Условие:

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

Входные данные
В первой строке входного файла содержится два целых числа 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++ Цикл for/Цикл while Помогите срочно пожалуйста...
C++ Выведите список школьников, рост которых превышает задаваемую величину, и определите их средние показатели роста и веса
C++ Расчет веса геометрических фигур из различных материалов
C++ Цикл: цикл for вообще никак не воспринимается транслятором
C++ Почему цикл на при 1 уходит в бесконечный цикл?
Задание на цикл с параметром и цикл с постусловием C++
Определить номер первого отрицательного и номер последовательного отрицательного элементов массива C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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