Цикл отрицательного веса

27.12.2013, 00:38. **Показов** 3739. **Ответов** 0

Помогите переделать решение, нашёл в интернете, но оно немного не подходит, а я никак не могу разобраться в коде и, следовательно, что-либо изменить. Можно обойтись без проверок, но очень помогли бы хоть какие-нибудь комментарии.

Условие:

Задан ориентированный граф, требуется определить, существует ли в нём цикл отрицательного веса. Использовать для этого метод Форда — Беллмана.

Входные данные
В первой строке входного файла содержится два целых числа n, m — число вершин и ребер графа соответственно (1 ≤ n ≤ 1000,0 ≤ m ≤ 100000). Далее следует описание m ребер графа a,b,c — ребро из вершины a в вершину b веса c (1 ≤ a,b ≤ n,−1000 ≤ c ≤ 1000).

Выходные данные
В первой строке файла выведите “YES”, если найден цикл отрицательного веса и — “NO” иначе. В случае положительного ответа далее выведите число ребер в цикле, затем номера самих ребер в порядке обхода по циклу. Ребра нумеруются с единицы в том порядке, в котором они следуют во входном файле.

Пример
Ввод
7 10
7 4 37
2 3 68
7 2 114
7 2 -69
7 2 58
1 6 112
7 6 103
2 7 -119
7 1 -107
1 5 23

Вывод
YES
2
4 8

Код, который я нашёл, выводит во второй строке количество вершин в искомом цикле (считая одинаковые первую и последнюю), а в третьей строке - вершины, входящие в этот цикл, в порядке обхода. Сделайте, пожалуйста, чтобы прога делала как у меня в условии, а то у меня уже мозг кипит. Надо было меньше пары прогуливать, тогда может и понял бы. От этой проги зависит допуск к экзамену, а в ночь с пятницы на субботу приём программ прекращается.

C++

#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;
}

Опции темы