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

Поиск отрицательых циклов в графе - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Обьясните что не так не могу понять http://www.cyberforum.ru/cpp-beginners/thread888257.html
программа должна менять цвет bmp файла но при запуске выдает ошибку что 2 неразрешимых внешних элемента есть и все я пробовал разобраться но не получилось коментрарии были даны на паре преподом но они особо не помогли( #include "stdafx.h" #include <stdio.h> #include <stdlib.h> typedef unsigned short int word; typedef unsigned int dword; //замена цвета прямоугольника на синий при...
C++ число цифр 3 в пятом представлении числа х По мат логике дано было задание: число цифр 3 в пятом представлении числа х. На бумаге задачу решил легко.Собственно вот решение Рисунок Надо написать под задачу программу на С++, а я в этом не понимаю.Может кто нибудь написать? http://www.cyberforum.ru/cpp-beginners/thread888247.html
C++ Ввод двумерного массива из файла
#include "stdafx.h" #include <stack> #include <iostream> #include <string> #include <algorithm> #include <locale> const int OPEN_VAL = 0; const int CLOSE_VAL = 1; const int START_VAL = -1;
C++ Блок-схема
Доброго дня,всем...Помогите пожалуйста составить 2 простенькие блок-схемы по следующим прогам #include<stdio.h> #include<iostream.h> #include<math.h> #include<stdlib.h> int main() { FILE *vivod; vivod=fopen("D:\lab2_11.txt","w");
C++ Инвентаризация http://www.cyberforum.ru/cpp-beginners/thread888212.html
В инвентарном файле содержатся сведения о том, изделия каких видов продукции и в каком количестве хранились на складе на момент последней инвентаризации. Сведения включают артикул изделия, наименование, единицы измерения, количество. Второй файл содержит сведения о поступлении и отпуске некоторых видов продукции, структура данных здесь дополнена типом операции (поступление или отпуск) и датой ее...
C++ Дана строка символов. Подсчитать общее число вхождений символов Привет всем. Дана строка символов. Подсчитать общее число вхождений символов .,+ в строку. Помогите реализовать данную программу. Нашел пару вариантов на форуме типа: #include <iostream> #include <iomanip> char * findchar(char * str, char ch){ for(;*str;++str) if (*str==ch) return str; return NULL; подробнее

Показать сообщение отдельно
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.06.2013, 17:21     Поиск отрицательых циклов в графе
barselona1994, Вот тебе для списка смежности, сначала вводится N - число вершин, затем M ( количество рёбер ). Потом рёбра (x, y, вес). Граф ориентирован.
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
#include <iostream>
#include <map>
#include <vector>
#include <limits>
#include <queue>
#include <stack>
 
using namespace std;    
 
#define ll long long
 
struct edge{
    int a, b;
    ll c;
};
 
int main(){         
    int n, m;
    cin >> n >> m;
    vector < edge > g;
    edge t;
    for (int i = 0 ; i < m; i++){
        scanf("%d%d%I64d", &t.a, &t.b, &t.c);
        g.push_back(t);
    }   
    const long long INF = LONG_MAX/2;
    vector <ll> d(n+1, 0), p(n+1, -1);
    int last;
    for (int i = 0 ; i < n; i++){
        last = -1;
        for (int j = 0; j < m; j++){
            //relax
            if (d[g[j].b] > d[g[j].a] + g[j].c){
                d[g[j].b] = max( -INF, d[g[j].a] + g[j].c);
                p[g[j].b] = g[j].a;
                last = g[j].b;
            }
        }
    }
    if (last != -1){
        printf("YES\n");
        for (int i = 0; i < n+2; i++){
            last = p[last];
        }
        if (p[last] == last){
            cout << 2 << endl << last << " " << last;
            return 0;
        }
        int t = last;
        stack<int> st;
        while (t != last || st.size() < 2){
            st.push(t);
            t = p[t];
        }
        st.push(last);
        cout << st.size() << endl;
        while (!st.empty()){
            printf("%d ", st.top());
            st.pop();
        }
    }else
        cout << "NO";
    return 0;
}
 
Текущее время: 22:07. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru