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

Поиск циклов в графе. Поиск центра взвешенного графа - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Списки:нужны или нет? http://www.cyberforum.ru/cpp-beginners/thread944104.html
Стоит ли изучать связные списки,они используются в дальнейшем? Может я туповат, но алгоритм их построения понять не могу. Уж больно все запутанно описывается в книжке. Пытался сам разбираться ,вот что вышло #include <iostream> using namespace std; class part { public: part *next; int item;
C++ Путь символа Здорова господа! Есть интересная задачка: "Проследите путь символа в вашей системе от клавиатуры до экрана на примере следующего кода:" char c; cin >>c; cout <<c<<endl; И как же его проследить???? http://www.cyberforum.ru/cpp-beginners/thread944099.html
C++ Ошибка: "case label not within a switch statement"
Здравствуйте, работая с оператором switch произошла ошибка case label '1' not within a switch statement case label '1' not within a switch statement case label '1' not within a switch statement Вот код std::cin >> pEnter;
C++ Время для функции генерирующей случайные величины
я написал функцию которая генерирует случайные величины в промежутке valarray<double> cRand::base_rnd(size_t N){ valarray<double> v; v.resize(N); int x,y; int x0 = time(0); x = fabs((a*x0 + c)%M); v = double(x)/M; for(size_t i = 1;i<N;i++){
C++ Конструктор класса http://www.cyberforum.ru/cpp-beginners/thread944077.html
class A{}; class B : public A { B(); }; B::B() : A() /// ДЛЯ ЧЕГО ТУТ :A() И ЧТО ЭТО ОЗНАЧАЕТ??? { }
C++ Конструктор класса Я не могу понять вот эту запись class A{}; class B : public A { подробнее

Показать сообщение отдельно
NurlashKO
87 / 87 / 14
Регистрация: 07.10.2012
Сообщений: 145
28.08.2013, 15:24     Поиск циклов в графе. Поиск центра взвешенного графа
2)
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
#include <iostream>
#include <cstdio>
 
using namespace std;
 
#define sz 1000
 
int n, a[sz][sz], d[sz], exc[sz], R, w;
 
int main()
{
    cin >> n;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];           // Читаем матрицу смежности графа, если ребра между вершинами нет то а[i][j] = -1
 
    //Находим кратчайшие расстояния между всеми парами вершын
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (a[i][j] != -1 && a[i][k] != -1 && a[k][j] != -1)
                    a[i][j] = min(a[i][k] + a[k][j], a[i][j]);
    //
    //Находим радиус графа, за одно подсчитываем эксцентриситет для каждой вершины
    R = (int)1e9;
    for (int i = 1; i <= n; i++)
    {
        w = 0;
        for (int j = 1; j <= n; j++)
        {
            if (a[i][j] != -1)
                w = max(w, a[i][j]);
        }
        exc[i] = w;
        R = min(R, exc[i]);
    }
    //
    //Если эксцентриситет вершины равен радиусу графа то эта вершина центр графа, выводим её.
    cout << "Center :" << endl;
    for (int i = 1; i <= n; i++)
        if (exc[i] == R)
            cout << i << " ";
}
Добавлено через 15 минут
1)
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
#include <iostream>
#include <cstdio>
 
using namespace std;
 
#define sz 1000
 
int n, a[sz][sz], c, d[sz], cnt;
 
bool check(int p, int t)
{
    if (p == t)
        return a[d[t]][d[1]];
    if (!a[d[p]][d[p + 1]])
        return false;
    return check(p + 1, t);
}
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];   //Читаем матрицу смежности, если есть ребро а[i][j] = 1, иначе 0
 
 
    for (int mask = 1; mask < (1 << n); mask++)     //Перебираем все возможные комбинации вершин (2 ^ n)
    {
        c = 0;
        for (int i = 0; i < n; i++)    //Выписываем вершины из текущей комбинации
            if (mask & (1 << i))
                d[++c] = i + 1;
        if (check(1, c))        //Если данные вершины образуют цикл, сообщаем об этом.
        {
            cnt++;
            cout << "Cycl " << cnt << " :" << endl;
            for (int i = 1; i <= c; i++)
                cout << d[i] << " ";
            cout << endl;
        }
    }
    
}
 
Текущее время: 05:42. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru