Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
0 / 0 / 0
Регистрация: 20.04.2012
Сообщений: 3
1

Радиус после удаления висячих вершин

28.04.2010, 18:48. Просмотров 644. Ответов 0
Метки нет (Все метки)

Необходимо найти радиус графа после удаления висячих вершин. Не могу найти ошибку. Результат всегда выдается либо 10000,либо 1010 почему-то))

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <fstream>
 
using namespace std;
 
const int Infinity = 10000; // бесконечность
const int Nmax = 100; // максимальное количество вершин графа
int W[Nmax][Nmax];
int n;
 
// Алгоритм Флойда - Уоршелла
void Floyd_Warshall()
{
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                W[i][j] = min(W[i][j], W[i][k] + W[k][j]);
}
 
// решение задачи
int Solve()
{
    Floyd_Warshall();
    int ecc, rad = Infinity;
    bool f;
    for (int i = 0; i < n; i++)
    {
        ecc = 0;
        f = false;
        for (int j = 0; j < n; j++)
        {
            if (i == j) continue;
            if ((ecc < W[i][j]) && (W[i][j] < Infinity)) 
            {
                ecc = W[i][j];
                f = true;
            }
        }
        if (!f) continue;
        if (rad > ecc) rad = ecc;
    }
    return rad;
}
 
// считываем граф, удаляем висячие вершины и заполняем матрицу W
void Read_And_Init()
{
    ifstream ifs;
    int M[Nmax][Nmax]; // матрица смежности
    ifs.open("input.txt");
    ifs >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            ifs >> M[i][j];
    ifs.close();
 
    // удаляем висячие вершины.
    int q, k;
    for (int i = 0; i < n; i++)
    {
        q = 0;
        for (int j = 0; j < n; j++)
            if (M[i][j] > 0) 
            {
                k = j;
                q++;
            }
        if (q == 1)
        {
            M[i][k] = 0;
            M[k][i] = 0;
        }
    }
 
    // записывам в матрицу W длины ребер
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (i == j)
                W[i][j] = 0;
            else 
                if (M[i][j] > 0)
                    W[i][j] = M[i][j];
                else
                    W[i][j] = Infinity;
}
 
void Print(int R)
{
    ofstream ofs;
    ofs.open("output.txt");
    ofs << R;
    ofs.close();
}
            
int main()
{
    int R;
    Read_And_Init();
    R = Solve();
    Print(R);
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.04.2010, 18:48
Ответы с готовыми решениями:

Есть дерево (ab) (bc) (cd) (ce) (bf) (fg) (fh) (fi) (bj). Составить список висячих вершин
Есть дерево ((ab) (bc) (cd) (ce) (bf) (fg) (fh) (fi) (bj)). Составить список висячих вершин

Найти радиус R описанной и радиус r вписанной окружности для данных вершин треугольника
2) Известны три точки - вершины треугольника АВС - А(20;15), В(-16;0), С(-8;-6). Найти радиус R...

Треугольник задан координатами вершин. Определить координаты и радиус описанной окружности
Помогите написать прогу! Треугольник задан координатами вершин. Определить координаты и радиус...

Для треугольника, заданного координатами вершин, вычислить радиус вписанной/описанной окружности
Треугольник задан координатами своих вершин. Составить программу для вычисления: 1)радиуса...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.04.2010, 18:48

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Дан треугольник по заданным координатам своих вершин.Определить радиус окружности возле треугольника
Дан треугольник по заданным координатам своих вершин.Определить радиус окружности возле...

Найти радиус большего из кругов описанных вокруг двух треугольников АВС и МРК, если известны координаты их вершин
Найти радиус большего из кругов описанных вокруг двух треугольников АВС и МРК, если известны...

Квадрат задан координатами своих вершин, определить радиус и длинну окружности, вписанной в квадрат
Квадрат задан координатами своих вершин, определить радиус и длинну окружности, вписанной в квадрат.

Найти координаты всех вершин правильного многоугольника, зная координаты центра и радиус описанной окружности.
Дан правильный N-угольник с центром в точке (X, Y) и с радиусом описанной окружности R. Найти...

Найти радиус и координаты центра вписанной в тетраэдр сферы, если известны координаты вершин тетраэдра
Хотелось бы узнать как решить эту задачу. Предполагаемое решение:

После компиляции VS2008 падает после удаления узла дерева, имеющего потомка
Вот код на Си: #include &lt;stdio.h&gt; #include &lt;string.h&gt; #include &lt;malloc.h&gt; #include &lt;conio.h&gt;...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.