Задача
Дан граф. Определить, есть ли в нем цикл отрицательного веса, и если да, то вывести его.
Входные данные
Первая строка содержит количество вершин графа n (1 ≤ n ≤ 100). В следующих n строках находится по n чисел — матрица смежности графа. Веса ребер не превышают по модулю 10000. Если ребра нет, соответствующее значение равно 100000.
Выходные данные
В первой строке выведите «YES«, если цикл существует, или «NO» в противном случае. При наличии цикла выведите во второй строке количество вершин в нем (считая одинаковыми первую и последнюю) и в третьей строке — вершины, входящие в этот цикл в порядке обхода. Если циклов несколько — выведите любой.
Тесты
Входные данные | Выходные данные: |
2 0 -1 -1 0 |
YES 3 1 2 1 |
4 0 2 0 9 2 0 6 0 0 6 0 -3 9 0 -3 0 |
YES 3 3 4 3 |
3 0 2 3 2 0 1 3 1 0 |
NO |
Код программы
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 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; struct edge{ int from, to, cost; }; const int INF = 1e9;; int main(){ int n; cin >> n; vector <edge> E; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ int x; cin >> x; if(x != 0 && x != 100000){ E.push_back({i,j,x}); } } } int x ; vector<int> d(n, INF), p(n, -1); d[0] = 0; for(int i = 0; i < n; i++){ x = -1; for(int j = 0; j < E.size(); j++){ int from = E[j].from; int to = E[j].to; int cost = E[j].cost; if(d[to] > d[from] + cost ){ d[to] = max(d[from] + cost, -INF); p[to] = from; x = to; } } } if(x == -1){ cout << "NO" << endl; }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 << "YES" << endl; cout << path.size() << endl; for(int i = 0; i < path.size(); i++){ cout << path[i] + 1; if(i != path.size()-1){ cout << ' '; } } cout << endl; } return 0; } |
Алгоритм решения:
Для решения данной задачи задействован алгоритм Беллмана-Форда, который позволяет проверить наличие или отсутствие цикла отрицательного веса в графе, а при его наличии — найти один из таких циклов. Создадим вектор, который будет содержать в себе элементы матрицы смежности графа. По определению смежных вершин графа, учитывая условие задачи (если ребра нет, соответствующее значение равно [latex]100000[/latex]), заполним этот вектор. Далее будем использовать алгоритм Беллмана-Форда. Если алгоритм даст отрицательный ответ на вопрос задачи, то выводим NO. Если цикл все-таки существует, то выводим YES. В вектор записываем вершины, входящие в цикл отрицательного веса. Далее выводим их количество, а затем и сами вершины в порядке обхода.
Для получения подробной информации об алгоритме Беллмана-Форда можно перейти по данной ссылке
Ссылка на засчитанное решение на e-olymp
Ссылка на условие задачи
Ссылка на решение задачи на ideone.com