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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Вычислить площадь http://www.cyberforum.ru/cpp-beginners/thread1058307.html
Помогите. Вычислить площадь трех прямоугольных треугольников, заданных гипотенузой и катетом. Добавлено через 32 минуты 8-)
C++ классы Не компилируется, помогите #include <iostream> #include <cstdlib> #include <vector> #include <map> // ��������� �������� typedef enum { S1, S2, S3 http://www.cyberforum.ru/cpp-beginners/thread1058304.html
Составить блок-схему C++
начертите блок схему по этому коду . пжлст #include <iostream> #include <vector> using namespace std; bool conectFile(){ if (!freopen ("input.txt", "r", stdin)){ fprintf (stderr, "File input.txt not found!");
C++ Как открыть программу через C++
Как открыть программу через C++ #include "stdafx.h"; #include <iostream> #include <string> #include <Windows.h> using namespace std; int main() { setlocale(LC_ALL, "Russian"); cout << "Нажмите Enter, чтобы открылась программа\n";
C++ Выясните, какая из букв слова, первая или последняя встречается в слове чаще http://www.cyberforum.ru/cpp-beginners/thread1058295.html
Задание:Выясните, какая из букв слова, первая или последняя встречается в слове чаще. Нужно чтобы программа при одинаковом количестве букв (к примеру мама) выводил, что нету такой буквы! Помогите пожалуйста, завтра сдавать последний срок( #include <iostream> #include <cctype> bool check(char, const char *);
C++ Вставка символа в строку на C++ Здравствуйте. Помогите пожалуйста найти ошибку. Нужно было написать функцию для вставки символа в массив. Задача элементарная, но что-то важное я упускаю. void insert(char *a,char c,int n) { char *t = new char; memset(t,c,strlen(a)+1); memcpy(t,a,n); for (int i = n+1;a!='\0';i++) { t = a; } подробнее

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

Условие:

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

Входные данные
В первой строке входного файла содержится два целых числа 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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 17:15. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru