ребро | 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 ≤ 100). В следующих n строках находится по n чисел, которые задают матрицу смежности графа. В ней -1 означает отсутствие ребра между вершинами, а любое неотрицательное число — присутствие ребра данного веса. На главной диагонали матрицы всегда расположены нули.

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

Вывести искомое максимальное кратчайшее расстояние.

#include <cstdlib>
#include <iostream>
 using namespace std;
 
int main(){
    int n;
    cin >> n;
    int a[n][n];
    long long maxr = 0;
    for( int i=0 ; i<n ; i++ ){
        for( int j=0 ; j<n ; j++ ){
            cin >> a[i][j];
        }
    }
    for( int k=0 ; k<n ; k++ ){
        for( int i=0 ; i<n ; i++ ){
            for( int j=0 ; j<n ; j++ ){
                if(i != j && a[i][k] != -1 && a[k][j] != -1){
                    if(a[i][j] == -1){
                        a[i][j] = a[i][k] + a[k][j];
                    }
                        else
                    {
                        a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
                    }
                }
            }
        }
    }
    for( int i=0 ; i<n ; i++ )
    {
        for( int j=0 ; j<n ; j++ )
        {
            if(a[i][j] > maxr) maxr = a[i][j];
        }
    }
    cout << maxr << endl;
}

#include <cstdlib>

#include <iostream>

using namespace std;

int main(){

int n;

cin >> n;

int a[n][n];

long long maxr = 0;

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

for( int j=0 ; j<n ; j++ ){

cin >> a[i][j];

}

for( int k=0 ; k<n ; k++ ){

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

for( int j=0 ; j<n ; j++ ){

if(i != j && a[i][k] != -1 && a[k][j] != -1){

if(a[i][j] == -1){

a[i][j] = a[i][k] + a[k][j];

}

else

{

a[i][j] = min(a[i][j], a[i][k] + a[k][j]);

}

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

{

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

{

if(a[i][j] > maxr) maxr = a[i][j];

}

cout << maxr << endl;

}

Задача на e-olimp

Тесты

input	output
4 0 5 9 -1 -1 0 2 8 -1 -1 0 7 4 -1 -1 0	16
5 0 5 5 6 -1 -1 0 9 8 4 -1 -1 0 3 8 6 -1 -1 0 5 -1 2 5 6 0	14

Решение:

По алгоритму Флойда (это алгоритм который способствует нахождению кротчайших расстояний между всеми вершинами взвешенного графа, благородя ему мы берем вершину и проверяем если возможно пройти через нее и это будет короче чем идти напрямик, то сохраняем длину пути через эту вершину ) мы проверяем на прочность все связи, иными словами — мы проходим все ребра и проверяем условие. Если существует альтернативный путь от одной вершины к другой, то будет ли он будет короче если да, то мы его заменяем. Таким алгоритмом мы находим все кротчайшие пути через вершины. Но в ответе должен быть максимальный из путей через вершины, поэтому приходится снова пройтись по путям через вершины (но это уже не ребра, а оптимальные длины путей) и найти кратчайший путь максимальной длины.

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

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

Tag Archives: ребро

e-olymp 1455. Цикл

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

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

Related Images:

e-olymp 975

Related Images: