алгоритм Беллмана-Форда | C++ для приматов

Задача

Дан граф. Определить, есть ли в нем цикл отрицательного веса, и если да, то вывести его.

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

Первая строка содержит количество вершин графа 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

Код программы

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

#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

Related Images:

Задача

В Летней Компьютерной Школе (ЛКШ) построили аттракцион «Лабиринт знаний». Лабиринт представляет собой n комнат, занумерованных от 1 до n, между некоторыми из которых есть двери. Когда человек проходит через дверь, показатель его знаний изменяется на определенную величину, фиксированную для данной двери. Вход в лабиринт находится в комнате 1, выход — в комнате n. Каждый ученик проходит лабиринт ровно один раз и попадает в ту или иную учебную группу в зависимости от количества набранных знаний (при входе в лабиринт этот показатель равен нулю). Ваша задача показать наилучший результат.

Пример

Входные данные	Выходные данные
2 2 1 2 5 1 2 -5	5
5 5 1 2 5 2 4 5 4 5 5 3 3 5 2 3 5	15
3 3 1 2 5 1 2 -5 2 2 6	🙁
3 3 1 2 2 2 3 3 3 1 4	🙂

Решение

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

struct edge
	{
		int start,finish,cost;
	};
	
int main()
	{
		int n,m;
		cin>>n>>m;
		vector<edge>e;
		for (int i=0;i<m;i++)
			{
				edge a;
				cin>>a.start>>a.finish>>a.cost;
				a.start--;
				a.finish--;
				e.push_back(a);
			}
		vector<int> length (n, INT_MIN);
		vector<int> p (n, -1);
		length[0] = 0;
		int x;
		for (int i=0;i<n;i++)
			{
				x = -1;
				for (int j=0;j<m;j++)
					if ((length[e[j].start]>INT_MIN)&&(length[e[j].finish]<length[e[j].start] + e[j].cost))
							{
								length[e[j].finish]=length[e[j].start] + e[j].cost;
								p[e[j].finish]=e[j].start;
								x=1;
							}
			}
		vector<int> path;
		int k=0;
		for (int i=n-1;i!=-1;i=p[i])
			{
				k++;
				path.push_back (i);
				if(k>n) break;
			}
		if(length[n-1]==INT_MIN) cout<<":("<<endl;
		else 
			 if((x!=-1)&&((path.back()!=0)||(path.front()!=n-1)||(k>n))) cout<<":)"<<endl;
			 else cout<<length[n-1]<<endl;
		return 0;
	}

#include <iostream>

#include <vector>

#include <climits>

using namespace std;

struct edge

{

int start,finish,cost;

};

int main()

{

int n,m;

cin>>n>>m;

vector<edge>e;

for (int i=0;i<m;i++)

{

edge a;

cin>>a.start>>a.finish>>a.cost;

a.start--;

a.finish--;

e.push_back(a);

}

vector<int> length (n, INT_MIN);

vector<int> p (n, -1);

length[0] = 0;

int x;

for (int i=0;i<n;i++)

{

x = -1;

for (int j=0;j<m;j++)

if ((length[e[j].start]>INT_MIN)&&(length[e[j].finish]<length[e[j].start] + e[j].cost))

{

length[e[j].finish]=length[e[j].start] + e[j].cost;

p[e[j].finish]=e[j].start;

x=1;

}

vector<int> path;

int k=0;

for (int i=n-1;i!=-1;i=p[i])

{

k++;

path.push_back (i);

if(k>n) break;

}

if(length[n-1]==INT_MIN) cout<<":("<<endl;

else

if((x!=-1)&&((path.back()!=0)||(path.front()!=n-1)||(k>n))) cout<<":)"<<endl;

else cout<<length[n-1]<<endl;

return 0;

}

Засчитанное решение.

Код на ideone.

Создадим вектор расстояний length на n элементов. Все элементы кроме 0-го приравниваем к минимальному числу. Нулевой элемент приравниваем к 0. Также создадим вектор p в котором будем хранить номер вершины из которой мы попали в текущую. Затем в цикле проходим по всем вершинам и в вектор length записываем расстояние за которое мы дошли в эту вершину. n-1 элемент вектора и будет ответом задачи. Затем мы восстанавливаем путь из нулевой вершины в последнюю, но будем это делать не более n раз. Затем проверяем, если в последней вершине значение не изменилось то выводим :(. Затем проверяем был ли в пути цикл, если да то выводи :), в противном случае выводим значение length[n-1].

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: алгоритм Беллмана-Форда

e-olymp 1455. Цикл

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

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

Related Images:

e-olymp 1454. Лабиринт знаний

Related Images: