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

Определить есть ли во взвешенном графе цикл отрицательного веса - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Посчитать длины кратчайших путей ориентированного графа http://www.cyberforum.ru/cpp-beginners/thread1782578.html
есть задача : задача №138 Алгоритм Форда-Беллмана (Время: 1 сек. Память: 16 Мб Сложность: 38%) Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют. Требуется посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин. ...
C++ Необходим материал для чтения и практики Всем доброго! Я почитал немало книг, перелопатил сайтов с практикой и видео по С++. Наступил какой-то период когда читай либо беру слишком сложно либо наоборот все понятно, да и практические только такие материалы попадаются. Не хочу останавливаться и идти по горизонтали, поэтому и обращаюсь и за лекционными материалами и за практическими указаниями. Все азы как бы уже поняты и в ООП, изучил и... http://www.cyberforum.ru/cpp-beginners/thread1782574.html
C++ Compair deque
есть два списка. Теперь мне нужно сравнить элементы если х <у то return (x+y) . я так думаю надо результат в 3 список записать как мне провести сравнение?? желательно с применением функциональных объектов deque<float>X; deque<float>Y; for (int i = 0; i < 7; ++i) X.push_back(i+(rand() % 25)); for (int i = 0; i < 7; ++i) Y.push_back(i + (rand() % 67)); copy(X.begin(), X.end(),...
C++ Передать значение из функции main в другую функцию
int Func(){ int a, b=10; int c=a+b; return c; } int main(){ int a=5; return 0;
C++ Как объявить friend функцию класса http://www.cyberforum.ru/cpp-beginners/thread1782486.html
как это оформить, чтобы работало // ----------> one.h #include "two.h" #ifndef ONE_H_INCLUDED #define ONE_H_INCLUDED #include <iostream> class A { int s;
C++ Создание пароля на вход в программу я написал программу по программированию, но препод решил усложнить и сказал сделать вход в программу с паролем. программа имеет одно рабочее окно, а как реализовать вход в программу с паролем я незнаю как( помогите пожалуйста подробнее

Показать сообщение отдельно
game1progg
31 / 1 / 0
Регистрация: 07.01.2016
Сообщений: 42
21.07.2016, 08:06  [ТС]
это ?
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
struct edge {
    int a, b, cost;
};
 
int n, m;
vector<edge> e;
const int INF = 1000000000;
 
void solve() {
    vector<int> d (n);
    vector<int> p (n, -1);
    int x;
    for (int i=0; i<n; ++i) {
        x = -1;
        for (int j=0; j<m; ++j)
            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 negative cycle found.";
    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);
            if (cur == y && path.size() > 1)  break;
        }
        reverse (path.begin(), path.end());
 
        cout << "Negative cycle: ";
        for (size_t i=0; i<path.size(); ++i)
            cout << path[i] << ' ';
    }
}
или это?
C++
1
2
3
4
5
for (int i=0; i<n; ++i)
    for (int j=0; j<n; ++j)
        for (int t=0; t<n; ++t)
            if (d[i][t] < INF && d[t][t] < 0 && d[t][j] < INF)
                d[i][j] = -INF;
можете мне цельный код написать?
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru