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

Отрицательный цикл - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Вычислить выражение по заданной формуле 2 (Функции) http://www.cyberforum.ru/cpp-beginners/thread514684.html
Приветствуйю друзья, вот продолжение вчерашней темы http://www.cyberforum.ru/cpp-beginners/thread514332-page2.html#post2772554 , вроде сделал правильно, но выдет ошибку... Сама задача №1: ...
C++ Чтение входных дат Доброе время суток Я работаю над домашним заданием по языку си. Программа должна переводить знаки кодированные в utf-8 до utf-16. Саму функцию которая это делает я уже написал,но у меня возникла... http://www.cyberforum.ru/cpp-beginners/thread514677.html
C++ Реализовать класс вектор
Здравствуйте, помогите с пунктом задачи: Реализовать класс вектор(двумерный), содержащий следующие поля: координаты вектора; методы класса: вывод вектора,сложение вычетание,скалярное...
Ошибка в функции C++
Здравствуйте, уважаемые знатоки! Итак, ящик в студию! Внимательно прочитайте код и найдите ошибки идиота! #include <iostream.h> #include <conio.h> #include <windows.h> #include <math.h>...
C++ Передача аргументов в ф-ию http://www.cyberforum.ru/cpp-beginners/thread514630.html
void test(const T& a) {} Это понятно, а что это за запись: void test(T const& a) {} И как понять ссылку на ссылку, видел в листинге одном...
C++ [C++] Дана строка. Получить подстроку расположенную... Помогите код дописать пожалуйста в лабе,.. нужно еще одно что бы условие выполнялось, нужно, чтобы имя файла, из которого читается строка, и имя файла, в который записывается, вводились из командной... подробнее

Показать сообщение отдельно
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
09.03.2012, 02:46
Niсe, у Вас решение основано на алгоритме Форда-Беллмана. Но зачем "столько много Форда-Беллмана" ? )
Раз его алгоритм:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
   d[0] = 0;
    for(int i = 0; i < n - 1; i++)
        {
        any = false;
                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] = d[e[j].a] + e[j].cost;
                                                p[e[j].b]=e[j].a ;
                                                any = true;
                                         }
    if (!any)  break;   
}
Два его алгоритм:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
        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;
                                }
        }
Вердикт: слишком много Форда-Беллмана - это плохо.

Оставьте так:
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;
}
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru