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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
Niсe
1 / 1 / 0
Регистрация: 09.12.2009
Сообщений: 30
#1

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

08.03.2012, 23:56. Просмотров 1280. Ответов 2
Метки нет (Все метки)

Помогите пожалуйста с задачкой, решил, но не проходит 1 тест.
Условие:

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 65536 KB.
Дан орграф. Определить, есть ли в нем цикл отрицательного веса, и если да, то вывести его.
Входные данные
Во входном файле в первой строке записаны числа N, M (1 <= N <= 1000; 0 <= M <= 10000), количество вершин графа и ребер соответственно.
Далее в M строках перечислены ребра тройками x_i, y_i, l_i, где l_i вес ребра (целое число по абсолютной величине не превосходящее 10^5).
Выходные данные
В первой строке выходного файла выведите YES, если цикл существует, или NO в противном случае. При его наличии выведите во второй строке количество вершин в искомом цикле (считая одинаковые первую и последнюю) и в третьей строке -- вершины, входящие в этот цикл, в порядке обхода.
Длина цикла не должна превосходить 10^6, цикл не обязан быть простым.
Пример
Ввод

2 4
1 1 0
1 2 -1
2 1 -1
2 2 0
Вывод
YES
3
1 2 1

Код:

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
65
66
67
68
69
70
71
72
73
74
75
76
#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;
    bool any, cycle = false;
    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, inf);
    vector<int> p (n);
    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;   
   }
    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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.03.2012, 23:56     Отрицательный цикл
Посмотрите здесь:

Выводит отрицательный ноль - C++
Столкнулся с такой проблемой: Ввожу с клавиатуры массив чисел действительных Сортирую их по модулю А когда вывожу, если изначально...

Отрицательный размер массива - C++
#include &lt;iostream&gt; #include &lt;windows.h&gt; using namespace std; int main() { setlocale(LC_ALL, &quot;russian&quot;); int...

Максимальный отрицательный элемент - C++
Помогите пожалуйста с этой задачей: Заданный одномерных массив, состоящий из N действительных элементов. Определить значение i номер...

Не меняет второй отрицательный - C++
Помогите с заменой, нужна программа завтра. Не меняет второй отрицательный! Что не так? # include &lt;iostream&gt; # include &lt;cstdlib&gt; #...

Отрицательный числа в rand() - C++
Как?

Найти минимальный отрицательный элемент - C++
Здравствуйте! Помогите пожалуйста! Дан одномерный массив, состоящий из N целочисленных элементов. 5.1. Ввести массив с клавиатуры. ...

Найти отрицательный корень уравнения - C++
Найти отрицательный корень уравнения e^x = 5x^2 Найти решение уравнения с точностью E= 0.0001 следующими методами: - дихотомии, -...

Первый отрицательный и минимальный эл массива - C++
Задание нужно найти первый отрицательный и минимальный элементы массива и обменять их местами. Задание то решил, но помогите решить ее с...

Определить первый отрицательный член - C++
Дано число L. Определить первый отрицательный член последовательности x1,x2,x3,..., где x1=L, xi=tg(xi-1).

Определить максимальный отрицательный элемент стека - C++
понимаю что боянщина, юзал поиск по сайту, но найти не смог. смысл: Создать стек из целых чисел. Оформить в виде функций: создание и...

Удалить из массива последний отрицательный элемент. - C++
Добрый день! Помогите с решением задачи. ...

Программа не указывает отрицательный знак в ответе - C++
Есть программа, которая считает в зависимости от условий и выводит в поля ввода промежуточный и итоговый ответ. Код программы ниже....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
DU
1482 / 1058 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
09.03.2012, 00:13     Отрицательный цикл #2
и что? вопрос то в чем?
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
09.03.2012, 02:46     Отрицательный цикл #3
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;
}
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru