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

Поиск отрицательых циклов в графе - C++

Восстановить пароль Регистрация
 
barselona1994
0 / 0 / 0
Регистрация: 04.10.2012
Сообщений: 88
02.06.2013, 17:13     Поиск отрицательых циклов в графе #1
подскажите пожалуйста, как определить, есть ли в графе отрицательные циклы....граф задаётся матрицей смежности
P.S очень срочно нужно.....завтра контрольная, а я не могу в этом разобраться(
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.06.2013, 17:13     Поиск отрицательых циклов в графе
Посмотрите здесь:

C++ Поиск ободов в графе
C++ поиск циклов в графе
Поиск на графе C++
Поиск всех циклов в неориентированном графе. C++
Поиск Ф-циклов в графе C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.06.2013, 17:21     Поиск отрицательых циклов в графе #2
barselona1994, Вот тебе для списка смежности, сначала вводится N - число вершин, затем M ( количество рёбер ). Потом рёбра (x, y, вес). Граф ориентирован.
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
63
64
#include <iostream>
#include <map>
#include <vector>
#include <limits>
#include <queue>
#include <stack>
 
using namespace std;    
 
#define ll long long
 
struct edge{
    int a, b;
    ll c;
};
 
int main(){         
    int n, m;
    cin >> n >> m;
    vector < edge > g;
    edge t;
    for (int i = 0 ; i < m; i++){
        scanf("%d%d%I64d", &t.a, &t.b, &t.c);
        g.push_back(t);
    }   
    const long long INF = LONG_MAX/2;
    vector <ll> d(n+1, 0), p(n+1, -1);
    int last;
    for (int i = 0 ; i < n; i++){
        last = -1;
        for (int j = 0; j < m; j++){
            //relax
            if (d[g[j].b] > d[g[j].a] + g[j].c){
                d[g[j].b] = max( -INF, d[g[j].a] + g[j].c);
                p[g[j].b] = g[j].a;
                last = g[j].b;
            }
        }
    }
    if (last != -1){
        printf("YES\n");
        for (int i = 0; i < n+2; i++){
            last = p[last];
        }
        if (p[last] == last){
            cout << 2 << endl << last << " " << last;
            return 0;
        }
        int t = last;
        stack<int> st;
        while (t != last || st.size() < 2){
            st.push(t);
            t = p[t];
        }
        st.push(last);
        cout << st.size() << endl;
        while (!st.empty()){
            printf("%d ", st.top());
            st.pop();
        }
    }else
        cout << "NO";
    return 0;
}
barselona1994
0 / 0 / 0
Регистрация: 04.10.2012
Сообщений: 88
02.06.2013, 17:25  [ТС]     Поиск отрицательых циклов в графе #3
Цитата Сообщение от Ternsip Посмотреть сообщение
barselona1994, Вот тебе для списка смежности, сначала вводится N - число вершин, затем M ( количество рёбер ). Потом рёбра (x, y, вес). Граф ориентирован.
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
63
64
#include <iostream>
#include <map>
#include <vector>
#include <limits>
#include <queue>
#include <stack>
 
using namespace std;    
 
#define ll long long
 
struct edge{
    int a, b;
    ll c;
};
 
int main(){         
    int n, m;
    cin >> n >> m;
    vector < edge > g;
    edge t;
    for (int i = 0 ; i < m; i++){
        scanf("%d%d%I64d", &t.a, &t.b, &t.c);
        g.push_back(t);
    }   
    const long long INF = LONG_MAX/2;
    vector <ll> d(n+1, 0), p(n+1, -1);
    int last;
    for (int i = 0 ; i < n; i++){
        last = -1;
        for (int j = 0; j < m; j++){
            //relax
            if (d[g[j].b] > d[g[j].a] + g[j].c){
                d[g[j].b] = max( -INF, d[g[j].a] + g[j].c);
                p[g[j].b] = g[j].a;
                last = g[j].b;
            }
        }
    }
    if (last != -1){
        printf("YES\n");
        for (int i = 0; i < n+2; i++){
            last = p[last];
        }
        if (p[last] == last){
            cout << 2 << endl << last << " " << last;
            return 0;
        }
        int t = last;
        stack<int> st;
        while (t != last || st.size() < 2){
            st.push(t);
            t = p[t];
        }
        st.push(last);
        cout << st.size() << endl;
        while (!st.empty()){
            printf("%d ", st.top());
            st.pop();
        }
    }else
        cout << "NO";
    return 0;
}
а может знаешь, как от списка смежности перейти к матрице смежности?) ....я допустим знаю , как от списка рёбер перейти к матрице смежности, а наоборот не знаю)
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.06.2013, 17:28     Поиск отрицательых циклов в графе #4
barselona1994, просто когда считываешь матрицу t.x = i; t.y = j; scanf("%I64d", &t.c); g.push_back(t); и не забудь что m = n * n тогда
barselona1994
0 / 0 / 0
Регистрация: 04.10.2012
Сообщений: 88
02.06.2013, 17:31  [ТС]     Поиск отрицательых циклов в графе #5
Цитата Сообщение от Ternsip Посмотреть сообщение
barselona1994, просто когда считываешь матрицу t.x = i; t.y = j; scanf("%I64d", &t.c); g.push_back(t); и не забудь что m = n * n тогда
а, что нужно добавить в этот код, чтобы вывести количество отрицательных циклов?
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.06.2013, 18:12     Поиск отрицательых циклов в графе #6
barselona1994, это совершенно другая задача.
Yandex
Объявления
02.06.2013, 18:12     Поиск отрицательых циклов в графе
Ответ Создать тему
Опции темы

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