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

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

Восстановить пароль Регистрация
 
game1progg
31 / 1 / 0
Регистрация: 07.01.2016
Сообщений: 38
19.07.2016, 09:23     Определить есть ли во взвешенном графе цикл отрицательного веса #1
(Время: 1 сек. Память: 16 Мб Сложность: 46%)
Дан взвешенный граф. Определить, есть ли в нем цикл отрицательного веса.

Входные данные

Во входном файле INPUT.TXT в первой строке записано число N (1 <= N <= 100) - количество вершин графа. В следующих N строках находится по N чисел - матрица смежности графа. Веса ребер не превышают по модулю 10000. Если ребра нет, соответствующее значение равно 100000.

Выходные данные

В выходной файл OUTPUT.TXT выведите "YES", если цикл существует, или "NO" в противном случае.

я сам нашёл подвох, это
Если ребра нет, соответствующее значение равно 100000.
прошу написать код, на темах теории графа и ничего лишнего
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.07.2016, 09:23     Определить есть ли во взвешенном графе цикл отрицательного веса
Посмотрите здесь:

Нахождение К путей Минимальной суммарной длины Во взвешенном графе с неотрицательными весами(Алгоритм Йена). C++
определить индекс первого отрицательного эл-та и присвоить значение индекса переменной C++
Гамильтонов цикл в графе C++
Найти цикл в графе C++
C++ Гамильтонов цикл в графе с выполненным условием Дирака
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
senich
61 / 61 / 23
Регистрация: 22.11.2012
Сообщений: 236
Записей в блоге: 1
19.07.2016, 10:02     Определить есть ли во взвешенном графе цикл отрицательного веса #2
google -> "цикл отрицательного веса" -> e-maxx.ru -> copy-past.
zer0mail
19.07.2016, 10:16
  #3

Не по теме:

Цитата Сообщение от game1progg Посмотреть сообщение
прошу написать код,
А какой смысл? acmp для поиска тех, кто сам может решить задачу, а не тех, кто может скопировать решение.

game1progg
31 / 1 / 0
Регистрация: 07.01.2016
Сообщений: 38
21.07.2016, 08:06  [ТС]     Определить есть ли во взвешенном графе цикл отрицательного веса #4
это ?
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;
можете мне цельный код написать?
Yandex
Объявления
21.07.2016, 08:06     Определить есть ли во взвешенном графе цикл отрицательного веса
Ответ Создать тему
Опции темы

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