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

Графы - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Потоки C++ http://www.cyberforum.ru/cpp-beginners/thread203782.html
Есть задача: 1) Смоделировать работу читателей и писателей на основе двух потоков. 2) Писатель генерирует структуру данных описывающую студента (ФИО, Возраст, Пол,…). 3) Читатель считывает структуру и подсчитывает ко-во людей одинакового возраста и пола. 4) Запись и чтение производится из буфера фиксированного размера(Например: 10 элементов). 5) Должен осуществляться вывод состояния буфера...
C++ Как изменить размер шара во время движения? Подскажите, плз, как изменить размер шара во время движения? Чтобы через какое-то время увеличился радиус. изначально мини-прожка такая : #include "TXLib.h" void DrawCircle (int x, int y, int r); void MoveCircle (int x, int y, int r, int v); int main() { txCreateWindow (1000, 700); http://www.cyberforum.ru/cpp-beginners/thread203777.html
C++ Интересная работа !!!!
задумка работы зделать игрушку ТИР ну я думаю вы все понимаете что ето и как в нее играть но вот делал ее делал и столкнулся с проблемой даже с несколькими сначала делал на с теперь делаю на с++ мне нужно сделать менюшку мишени и какуето функцию с подшетом очьков ну и тд и тп Помоготи вопрос жизни и смерти)) #include <iostream>
C++ Определить количество классов эквивалентных строк данной прямоугольной матрицы
Определить количество классов эквивалентных строк данной прямоугольной матрицы. Строки считать эквивалентными, если равны суммы их элементов.
C++ массив http://www.cyberforum.ru/cpp-beginners/thread203769.html
помогите символьный массив состоящий из чисел , перевести в целочисленный массив и вывсети на экран , на си Добавлено через 9 минут помогите символьный массив состоящий из чисел , перевести в целочисленный массив и вывсети на экран , на си с помощью atoi
C++ Разложение в ряд #include <stdio.h> #include <math.h> int main () { double a,b,x,k; //k - to4noe printf("BBegute x\n"); scanf("%lf",&x); printf("BBeguTe LLIar\n"); scanf("%lf",&a); printf("BBeguTe x KoHe4Hoe\n"); подробнее

Показать сообщение отдельно
Mr.X
Эксперт С++
 Аватар для Mr.X
2803 / 1579 / 247
Регистрация: 03.05.2010
Сообщений: 3,673
07.12.2010, 17:35     Графы
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
//////////////////////////////////////////////////////////////////////////////////////
//По системе односторонних дорог определить, есть ли в ней город, из которого 
//можно добраться до каждого из остальных городов, проезжая не более 100 км.
//////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <limits>
#include <map>
#include <set>
#include <string>
#include <vector>
//////////////////////////////////////////////////////////////////////////////////////
typedef std::string                    T_str;
typedef T_str                          T_vertice;
typedef std::set<T_vertice>            T_vertices_set;
typedef std::vector<T_vertice>         T_vertices;
typedef T_vertices                     T_arc;
typedef std::set<T_arc>                T_arcs_set;
typedef int                            T_weight;
typedef std::map<T_arc, T_weight>      T_arcs_weights;
typedef std::map<T_vertice, T_weight>  T_row;
typedef std::map<T_vertice, T_row>     T_adjacency_matr;
//////////////////////////////////////////////////////////////////////////////////////
struct T_greater_in_row
{
    T_row  row_;
    //------------------------------------------------------------------------
    T_greater_in_row(T_row  row) : row_(row)
    {}
    //------------------------------------------------------------------------
    bool operator() (T_vertice  A, T_vertice  B)                  
    {
        return row_[A] > row_[B];
    }
};
//////////////////////////////////////////////////////////////////////////////////////
void  print_matr
    (
        const T_adjacency_matr&  matr,
        const T_weight           WEIGHT_MAX,
        const T_str              INFINITY_NAME
    )
{  
    for(T_adjacency_matr::const_iterator  vert_row_it = matr.begin(); 
        vert_row_it != matr.end(); ++vert_row_it)
    {
        for(T_row::const_iterator  vert_weight_it = vert_row_it->second.begin();
            vert_weight_it != vert_row_it->second.end(); ++vert_weight_it)
        {
            if(vert_weight_it->second == WEIGHT_MAX)
            {
                std::cout << '\t'
                          << INFINITY_NAME;
            }
            else
            {
                std::cout << '\t'
                          << vert_weight_it->second;
            }
        }
        std::cout << std::endl
                  << std::endl
                  << std::endl;
    }
}
//////////////////////////////////////////////////////////////////////////////////////
T_vertices  get_vertices(const T_arcs_set&  arcs_set)
{
    T_vertices_set  vertices_set;
    for(T_arcs_set::const_iterator  arc_it = arcs_set.begin(); arc_it != arcs_set.end();
        ++ arc_it)
    {
        vertices_set.insert(*arc_it->begin());
        vertices_set.insert(*arc_it->rbegin());
    }
    return T_vertices(vertices_set.begin(), vertices_set.end()); 
}
//////////////////////////////////////////////////////////////////////////////////////
T_adjacency_matr  get_adjacency_matr
    (
        const T_vertices&      vertices, 
        const T_arcs_weights&  arcs_weights,
        const T_weight         WEIGHT_MAX
    )
{
    T_adjacency_matr  adjacency_matr;
    for(size_t  i = 0; i < vertices.size(); ++i)
    {
        for(size_t  j = 0; j < vertices.size(); ++j)
        {
            adjacency_matr[vertices[i]][vertices[j]] = WEIGHT_MAX;
        }
    }
 
    for(T_arcs_weights::const_iterator   arcs_weights_elem_it = arcs_weights.begin(); 
        arcs_weights_elem_it != arcs_weights.end(); ++arcs_weights_elem_it)
    {
        adjacency_matr
            [arcs_weights_elem_it->first.front()]
            [arcs_weights_elem_it->first.back() ] = arcs_weights_elem_it->second;
    }
    return  adjacency_matr;
}
//////////////////////////////////////////////////////////////////////////////////////
T_row  dijkstra
    (
        const T_vertice&   vertice_start,
        T_vertices         vertices,
        T_adjacency_matr&  adjacency_matr,
        const T_weight     WEIGHT_MAX
    )
{    
    T_row       weights_min_from_vert_start = adjacency_matr[vertice_start];     
    T_vertices  S;
    S.push_back     (vertice_start);
    vertices.erase  (std::find(vertices.begin(), vertices.end(), vertice_start));    
    while(!vertices.empty())
    {
        //Из элементов vertices выбираем тот, для которого значение weights_min_from_vert_start
        //минимально.
        std::make_heap(vertices.begin(), vertices.end(), 
                       T_greater_in_row(weights_min_from_vert_start));
 
        T_vertice  w = vertices.front();
 
        S.push_back     (w);
        vertices.erase  (vertices.begin());
        for(T_vertices::const_iterator  v_it = vertices.begin();
            v_it != vertices.end(); ++v_it)
        {
            T_weight&  for_w    = weights_min_from_vert_start  [w];
            T_weight&  for_v    = weights_min_from_vert_start  [*v_it];
            T_weight&  for_w_v  = adjacency_matr               [w][*v_it];
 
            if(   for_w    != WEIGHT_MAX  
               && for_w_v  != WEIGHT_MAX
               && for_w + for_w_v < for_v)
            {
                for_v = for_w + for_w_v;
            }
        }
    }
    return  weights_min_from_vert_start;
}
//////////////////////////////////////////////////////////////////////////////////////
void print_vertice_distant_not_further_than
    (
        const T_weight     max_path_weight,
        const T_vertices&  vertices,
        T_adjacency_matr&  adjacency_matr,
        const T_weight     WEIGHT_MAX
    )
{    
    for(T_vertices::const_iterator  v_it = vertices.begin();
        v_it != vertices.end(); ++v_it)
    {
        T_row  weights_min_from_v = dijkstra
                                        (
                                            *v_it,
                                            vertices,
                                            adjacency_matr,
                                            WEIGHT_MAX
                                        );
 
        T_vertices  vertices_for_v(vertices);
        std::sort(vertices_for_v.begin(), vertices_for_v.end(), 
                  T_greater_in_row(weights_min_from_v));
 
        //Удаляем первую вершину, так как это сама *v_it, расстояние до которой
        //от самой себя бесконечность.
        vertices_for_v.erase(vertices_for_v.begin());
 
        if(weights_min_from_v[vertices_for_v.front()] <= max_path_weight)
        {
            std::cout << "Город, расположенный от остальных не далее "
                      << max_path_weight 
                      << " км: "
                      << *v_it
                      << "."
                      << std::endl;
            return;
        }
 
    }
    std::cout << "В данной системе дорог нет города, "               
              << "расположенного от остальных не далее "
              << max_path_weight 
              << " км."
              << std::endl;
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    int n = 0;
    do
    {
        std::cout << "Введите количество дуг ориентированного взвешенного графа > 0: ";
        std::cin >> n;
    }while(n <= 0);
 
    T_arcs_set      arcs_set;
    T_arcs_weights  arcs_weights;
    const T_weight  WEIGHT_MAX = std::numeric_limits<T_weight>::max();
    const T_str     INFINITY_NAME = "INF";
    std::cout << "Введите "
              << n
              << " дуг ориентированного взвешенного графа."
              << std::endl
              <<"Вершины в дуге не должны быть одинаковыми.";
    do
    {
        std::cout << std::endl
                  << "дуга #"
                  << arcs_set.size() + 1
                  << ":"
                  << std::endl
                  << '\t'
                  << "начало  : ";
        T_vertice  v1;
        std::cin >> v1;
        T_arc  arc_cur;
        arc_cur.push_back(v1);
        
        T_vertice  v2;
        std::cout << '\t'
                  << "конец   : ";
        std::cin >> v2;        
        arc_cur.push_back(v2);        
        if(   arc_cur.size() == 2
           && arc_cur.front() != arc_cur.back())
        {
            if(arcs_set.insert(arc_cur).second)
            {
                T_weight  arc_weight;
                do
                {
                    std::cout << '\t'
                              << '\t'
                              << "вес >= 0"                              
                              << ": ";
                    std::cin >> arc_weight;
                }while(arc_weight < 0 || WEIGHT_MAX <= arc_weight);
                arcs_weights[arc_cur] = arc_weight;
            }
        }        
    }while(static_cast<int>(arcs_set.size()) < n);
 
    T_vertices  vertices = get_vertices(arcs_set);
 
    T_adjacency_matr  adjacency_matr = get_adjacency_matr(vertices, arcs_weights, WEIGHT_MAX);
 
    std::cout << std::endl
              << "Матрица смежности графа ("
              << INFINITY_NAME 
              << " означает бесконечность):"
              << std::endl;
 
    print_matr(adjacency_matr, WEIGHT_MAX, INFINITY_NAME);
 
    std::cout << "Вершины графа:"
              << std::endl
              << '\t';
 
    std::copy(vertices.begin(), vertices.end(), 
              std::ostream_iterator<T_vertice>(std::cout, "\t"));
    std::cout << std::endl;
 
    const int  max_path_weight = 100;
    
    print_vertice_distant_not_further_than
        (
            max_path_weight,
            vertices,
            adjacency_matr,
            WEIGHT_MAX
        );
}
 
Текущее время: 12:29. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru